1. Идея

Нужно найти минимальную грузоподъёмность парома cap, чтобы все грузы, идущие в фиксированном порядке, удалось перевезти не более чем за D дней.

Если грузоподъёмность известна, можно легко проверить, хватит ли её:

• в каждый день загружаем подряд идущие грузы,
• как только следующий груз уже не помещается, начинаем новый день.

Такая проверка делается жадно за один проход по массиву.

Дальше замечаем важное свойство: если некоторая грузоподъёмность cap подходит, то любая большая грузоподъёмность тоже подходит. Значит, ответ можно искать двоичным поиском по значению cap.

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

Наблюдение 1. Нижняя граница ответа

Паром должен уметь перевезти любой отдельный груз, значит

• cap >= max(a_i).

Иначе самый тяжёлый груз невозможно перевезти вообще.

Наблюдение 2. Верхняя граница ответа

Если взять

• cap = sum(a_i),

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

Наблюдение 3. Как проверить фиксированную грузоподъёмность

Пусть дана грузоподъёмность cap.

Идём по грузам слева направо и поддерживаем текущий суммарный вес cur в текущем дне:

• если cur + a[i] <= cap, добавляем груз в текущий день;
• иначе начинаем новый день и кладём этот груз первым в новый день.

Так мы получаем минимально возможное число дней для данной грузоподъёмности, потому что каждый день заполняется максимально возможным количеством подряд идущих грузов.

Наблюдение 4. Монотонность

Если can(cap) означает, что грузоподъёмности cap хватает, то:

• если can(cap) = true, то и для любого cap2 > cap тоже будет true;
• если can(cap) = false, то для любого cap2 < cap тоже будет false.

Это и позволяет применить двоичный поиск по ответу.

3. Алгоритм

1. Считываем n, D и массив a.
2. Устанавливаем границы двоичного поиска:
   • left = max(a),
   • right = sum(a).
3. Реализуем функцию can(cap):
   • начинаем с days = 1 и cur = 0;
   • последовательно добавляем грузы в текущий день;
   • если очередной груз не помещается, увеличиваем days и начинаем новый день с этого груза.
   • в конце проверяем, что days <= D.
4. Пока left < right:
   • берём mid = (left + right) // 2;
   • если can(mid) истинно, пробуем уменьшить ответ: right = mid;
   • иначе нужно увеличить грузоподъёмность: left = mid + 1.
5. После завершения цикла left и будет минимальной подходящей грузоподъёмностью.

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

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

Почему жадная проверка считает минимальное число дней

Для фиксированного cap в каждый день мы кладём максимально длинный возможный подряд идущий отрезок грузов.

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

Следовательно, жадная стратегия действительно даёт минимальное число дней при заданном cap.

Почему есть монотонность

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

Следовательно:

• все неподходящие значения идут слева,
• все подходящие значения идут справа.

То есть множество ответов имеет вид:

• false false false ... false true true true ... true.

На таком массиве значений двоичный поиск находит первую позицию true, то есть минимальную подходящую грузоподъёмность.

Почему итоговое значение — ответ

Двоичный поиск поддерживает инвариант:

• ответ всегда лежит в отрезке [left, right].

Когда can(mid) истинно, mid уже подходит, поэтому ответ не больше mid, и можно сузить отрезок до [left, mid].

Когда can(mid) ложно, mid не подходит, значит ответ строго больше mid, и можно перейти к [mid + 1, right].

Когда left == right, в отрезке остаётся ровно одно значение — это и есть минимальная подходящая грузоподъёмность.

5. Сложность

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

• Проверка can(cap) работает за O(n).
• Двоичный поиск делает O(log S) итераций.

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

• O(n log S).

Память:

• O(n) на хранение массива грузов.

6. Код на C++17

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

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

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

    auto can = [&](long long cap) {
        int days = 1;
        long long cur = 0;
        for (int i = 0; i < n; i++) {
            if (cur + a[i] <= cap) {
                cur += a[i];
            } else {
                days++;
                cur = a[i];
            }
        }
        return days <= D;
    };

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

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

7. Код на Python 3

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

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

def can(cap):
    days = 1
    cur = 0
    for x in a:
        if cur + x <= cap:
            cur += x
        else:
            days += 1
            cur = x
    return days <= D

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

print(left)