Делёж по кускам — разбор задачи

1. Идея

Нужно разбить массив на k + 1 подряд идущих непустых кусков так, чтобы минимальная сумма среди этих кусков была как можно больше.

Это типичная задача на поиск по ответу:

• пусть мы проверяем, можно ли добиться того, чтобы каждый кусок имел сумму не меньше x;
• если это возможно, то, возможно, получится и для большего x;
• если невозможно, то для ещё большего x тоже невозможно.

Значит, ответ можно искать бинарным поиском по значению минимальной суммы.

2. Наблюдения

Наблюдение 1

Если некоторое значение x достижимо, то любое меньшее значение тоже достижимо.

Почему? Если мы уже умеем разбить плитку так, что каждый кусок имеет сумму хотя бы x, то тем более каждый кусок имеет сумму хотя бы любого меньшего числа.

Это и даёт монотонность, нужную для двоичного поиска.

Наблюдение 2

Как проверить, можно ли получить хотя бы k + 1 кусков с суммой не меньше x?

Нужно идти слева направо и накапливать сумму текущего куска. Как только сумма стала не меньше x, выгодно сразу завершить этот кусок и начать новый.

Почему это выгодно? Потому что если текущий кусок уже подходит, нет смысла делать его длиннее: лишние элементы лучше оставить следующим кускам.

Такой жадный способ даёт максимальное возможное число кусков с суммой не меньше x.

Наблюдение 3

В задаче нужно сделать ровно k разрезов, то есть получить ровно k + 1 кусок.

Но в проверке достаточно понять, можно ли получить не меньше чем k + 1 кусков с суммой хотя бы x.

Почему так можно? Если удалось получить больше кусков, всегда можно объединить несколько соседних кусков. После объединения сумма не уменьшится, а число кусков станет меньше. Значит, из разбиения на >= k + 1 хороших кусков можно получить разбиение ровно на k + 1 хороших кусков.

3. Алгоритм

Обозначим needPieces = k + 1.

Проверка can(x)

Проверим, можно ли получить хотя бы needPieces кусков, каждый с суммой не меньше x.

• cur = 0 — сумма текущего собираемого куска
• pieces = 0 — сколько подходящих кусков уже получили

Идём по всем элементам массива:

• прибавляем очередное значение к cur;
• если cur >= x, то:
  • увеличиваем pieces;
  • сбрасываем cur = 0, начиная собирать следующий кусок.

В конце проверяем: pieces >= needPieces.

Бинарный поиск

Ищем максимальное x, для которого can(x) истинно.

Границы:

• left = 1
• right = sum(a) — больше общей суммы ответ быть не может

Пока left <= right:

• mid = (left + right) // 2
• если can(mid):
  • ответ можно увеличить, запоминаем mid
  • left = mid + 1
• иначе:
  • right = mid - 1

Итоговый сохранённый ответ и будет максимальной возможной сладостью минимального куска.

4. Почему это работает

Докажем корректность решения.

Лемма 1

Для фиксированного x жадная проверка строит максимально возможное число кусков с суммой не меньше x.

Почему?

Как только накопленная сумма стала не меньше x, мы сразу заканчиваем кусок. Если бы мы продолжили добавлять элементы в этот кусок, то только забрали бы элементы у следующих кусков. Это не может увеличить число подходящих кусков, а иногда может только уменьшить его.

Значит, раннее завершение каждого возможного куска оптимально для максимизации количества кусков.

Лемма 2

Если жадная проверка получила pieces >= k + 1, то существует разбиение ровно на k + 1 кусков, каждый с суммой не меньше x.

Почему?

Если кусков получилось больше, чем нужно, можно объединять соседние куски. При объединении сумма нового куска равна сумме двух старых, то есть она не меньше x. Повторяя объединения, получим ровно k + 1 кусков.

Лемма 3

Если жадная проверка получила pieces < k + 1, то разбиение на k + 1 кусков с суммой не меньше x не существует.

Почему?

По лемме 1 жадный алгоритм даёт максимальное число подходящих кусков. Если даже он не смог получить k + 1, то никакой другой способ тоже не сможет.

Лемма 4

Предикат can(x) монотонен: если can(x) истинно, то can(y) истинно для любого y <= x.

Это очевидно: требование к минимальной сумме становится слабее.

Вывод

Так как:

• can(x) корректно проверяется жадно,
• предикат монотонен,

можно применять бинарный поиск по ответу и находить максимальное допустимое значение x.

Следовательно, алгоритм находит правильный ответ.

5. Сложность

Пусть S = sum(a).

• Одна проверка can(x) работает за O(n).
• Бинарный поиск делает O(log S) проверок.

Итого:

• время: O(n log S)
• память: O(n)

При n <= 2 * 10^5 это укладывается в ограничения.

6. Код на C++17

#include <iostream>
#include <vector>
using namespace std;

bool can(const vector<long long>& a, int needPieces, long long x) {
    long long cur = 0;
    int pieces = 0;
    for (long long v : a) {
        cur += v;
        if (cur >= x) {
            pieces++;
            cur = 0;
        }
    }
    return pieces >= needPieces;
}

int main() {
    int n, k;
    cin >> n >> k;

    vector<long long> a(n);
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }

    int needPieces = k + 1;
    long long left = 1, right = sum, ans = 1;

    while (left <= right) {
        long long mid = left + (right - left) / 2;
        if (can(a, needPieces, mid)) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    cout << ans << '\n';
    return 0;
}

7. Код на Python 3

n, k = map(int, input().split())
a = list(map(int, input().split()))

need_pieces = k + 1
total = sum(a)

def can(x):
    cur = 0
    pieces = 0
    for v in a:
        cur += v
        if cur >= x:
            pieces += 1
            cur = 0
    return pieces >= need_pieces

left = 1
right = total
ans = 1

while left <= right:
    mid = (left + right) // 2
    if can(mid):
        ans = mid
        left = mid + 1
    else:
        right = mid - 1

print(ans)