Разбиение на отрезки

1. Идея

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

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

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

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

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

Наблюдение 1. Ответ не может быть меньше max(a)

Если какой-то участок имеет объём работы a_i, то он целиком должен попасть одному маляру. Значит, максимальная нагрузка никак не может быть меньше самого большого элемента массива.

То есть нижняя граница ответа:

left = max(a)

Наблюдение 2. Ответ не может быть больше sum(a)

Если отдать всю ленту одному маляру, нагрузка будет равна сумме всех элементов. В нашей задаче маляров больше, но это всё равно корректная верхняя граница.

То есть верхняя граница ответа:

right = sum(a)

Наблюдение 3. Проверка для фиксированного X делается жадно

Хотим понять: можно ли разбить массив на отрезки так, чтобы сумма каждого была не больше X.

Самый выгодный жадный подход такой:

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

Так мы получаем минимально возможное число отрезков при ограничении X.

Почему минимальное? Потому что каждый раз мы стараемся сделать текущий отрезок максимально длинным. Если разрезать раньше, отрезков станет только больше.

Наблюдение 4. Почему достаточно проверки parts <= k

В условии требуется ровно k непустых отрезков. А в проверке используется условие parts <= k.

Это корректно. Если мы смогли разбить массив на parts отрезков, где parts <= k, то всегда можно дополнительно разрезать некоторые отрезки на более мелкие, пока не получим ровно k отрезков.

Почему это возможно?

• все отрезки непустые;
• k <= n;
• любой отрезок длины хотя бы 2 можно разбить на два непустых подряд идущих отрезка;
• сумма каждого нового отрезка не превысит сумму исходного, а значит, не превысит X.

3. Алгоритм

1. Считываем n, k и массив a.
2. Устанавливаем границы двоичного поиска:
   • left = max(a)
   • right = sum(a)
3. Пока left < right:
   • берём mid = (left + right) // 2;
   • проверяем, можно ли разбить массив на не более чем k отрезков так, чтобы сумма каждого не превышала mid;
   • если можно, сдвигаем правую границу: right = mid;
   • иначе сдвигаем левую границу: left = mid + 1.
4. После завершения двоичного поиска left и будет ответом.

Как работает проверка can_split(mid)

Поддерживаем:

• parts — сколько отрезков уже получилось;
• current — сумма текущего отрезка.

Для каждого x из массива:

• если x > mid, то такой mid вообще невозможен;
• если current + x <= mid, добавляем x в текущий отрезок;
• иначе начинаем новый отрезок:
  • parts += 1
  • current = x

В конце проверяем, что parts <= k.

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

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

Лемма 1. Жадная проверка для фиксированного limit строит разбиение с минимально возможным числом отрезков

Рассмотрим процесс:

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

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

Следовательно, жадный алгоритм действительно даёт минимальное число отрезков среди всех допустимых разбиений при данном limit.

Лемма 2. Если жадная проверка получила parts <= k, то существует разбиение ровно на k отрезков

Жадный алгоритм уже построил допустимое разбиение, где сумма каждого отрезка не больше limit.

Если parts = k, всё готово.

Если parts < k, можно разбить некоторые отрезки дополнительно. Так как всего элементов n, а k <= n, можно получить ровно k непустых отрезков. При этом суммы новых отрезков не превысят сумму исходного отрезка, а значит, не превысят limit.

Значит, условие parts <= k действительно эквивалентно существованию разбиения ровно на k отрезков.

Лемма 3. Если некоторый limit подходит, то любой больший limit тоже подходит

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

Значит, ответ обладает монотонностью:

• все слишком маленькие значения не подходят;
• начиная с некоторого значения, все подходят.

Следствие

Раз есть монотонность, можно искать минимальное подходящее значение двоичным поиском.

Итог

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

5. Сложность

Пусть сумма элементов может быть большой, но двоичный поиск делает O(log(sum(a))) итераций.

Каждая проверка проходит по массиву один раз, то есть работает за O(n).

Итоговая сложность:

• по времени: O(n log(sum(a)))
• по памяти: O(n)

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

6. Код на C++17

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool can_split(const vector<long long>& a, int k, long long limit) {
    int parts = 1;
    long long current = 0;

    for (long long x : a) {
        if (x > limit) {
            return false;
        }
        if (current + x <= limit) {
            current += x;
        } else {
            parts++;
            current = x;
        }
    }

    return parts <= k;
}

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

    vector<long long> a(n);
    long long left = 0;
    long long right = 0;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        left = max(left, a[i]);
        right += a[i];
    }

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

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

7. Код на Python 3

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

left = max(a)
right = sum(a)

def can_split(limit):
    parts = 1
    current = 0
    for x in a:
        if x > limit:
            return False
        if current + x <= limit:
            current += x
        else:
            parts += 1
            current = x
    return parts <= k

while left < right:
    mid = (left + right) // 2
    if can_split(mid):
        right = mid
    else:
        left = mid + 1

print(left)