1. Идея

Нужно найти минимальную целую скорость s, при которой все кучи можно съесть за H часов.

Если скорость фиксирована, легко посчитать, сколько часов потребуется:

• для кучи размера a_i нужно ceil(a_i / s) часов;
• общее время — сумма по всем кучам.

Тогда задача сводится к такой:

• умеем проверять, подходит ли скорость s;
• хотим найти минимальную подходящую скорость.

Это классическая ситуация для двоичного поиска по ответу.

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

1. Сколько часов нужно на одну кучу

За час можно есть только из одной кучи и не более s бананов.

Значит, для кучи из a_i бананов потребуется:

• 1 час, если a_i <= s;
• 2 часа, если s < a_i <= 2s;
• и так далее.

То есть число часов равно ceil(a_i / s).

В коде это удобно считать так:

• (a_i + s - 1) / s в C++;
• (a_i + s - 1) // s в Python.

2. Монотонность

Если увеличить скорость, часов потребуется не больше.

Иначе говоря:

• если скорость s подходит, то любая скорость больше s тоже подходит;
• если скорость s не подходит, то любая скорость меньше s тоже не подходит.

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

3. Границы поиска

Минимальная возможная скорость — 1.

Максимальная возможная скорость — max(a):

• если за час можно съесть целую самую большую кучу, то любую кучу можно съесть за один час;
• тогда суммарно понадобится ровно n часов;
• по условию H >= n, значит такая скорость точно подходит.

3. Алгоритм

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

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

Обозначим через f(s) количество часов, нужное при скорости s.

Тогда:

• для каждой кучи время равно ceil(a_i / s);
• при увеличении s значение ceil(a_i / s) не возрастает;
• значит и вся сумма f(s) не возрастает.

Следовательно, существует граница:

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

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

Почему проверка корректна:

• каждая куча требует ровно ceil(a_i / s) часов, потому что за час можно убрать не более s бананов;
• кучи независимы по времени, поэтому общее число часов — сумма по кучам;
• если эта сумма не превышает H, значит успеть можно;
• если превышает, значит при такой скорости успеть нельзя.

Поэтому двоичный поиск по этой проверке действительно находит минимальную подходящую скорость.

5. Сложность

Пусть M = max(a).

Одна проверка скорости работает за O(n), потому что нужно пройти по всем кучам.

Двоичный поиск делает O(log M) шагов.

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

• O(n log M) по времени;
• O(n) по памяти на хранение массива.

6. Код на C++17

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

using namespace std;

int main() {
    int n;
    long long H;
    cin >> n >> H;

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

    long long left = 1, right = mx, answer = mx;

    while (left <= right) {
        long long mid = left + (right - left) / 2;

        long long hours = 0;
        for (int i = 0; i < n; i++) {
            hours += (a[i] + mid - 1) / mid;
            if (hours > H) break;
        }

        if (hours <= H) {
            answer = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

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

7. Код на Python 3

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

left = 1
right = max(a)
answer = right

while left <= right:
    mid = (left + right) // 2

    hours = 0
    for x in a:
        hours += (x + mid - 1) // mid
        if hours > H:
            break

    if hours <= H:
        answer = mid
        right = mid - 1
    else:
        left = mid + 1

print(answer)