1. Идея

Нужно выбрать максимальную высоту пилы h, чтобы после срезания верхушек суммарно получилось не меньше M древесины.

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

Значит, ответ можно искать двоичным поиском по значению h.

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

Для фиксированной высоты h легко посчитать, сколько древесины получится:

• если a_i > h, дерево даёт a_i - h;
• иначе дерево ничего не даёт.

То есть суммарная древесина равна сумме всех max(0, a_i - h).

Теперь важное свойство:

• если при высоте h древесины хватает, то при любой меньшей высоте тоже хватит;
• если при высоте h древесины не хватает, то при любой большей высоте тоже не хватит.

Это монотонность, а значит подходит двоичный поиск.

Границы поиска такие:

• минимальная возможная высота пилы: 0;
• максимальная разумная высота пилы: max(a).

Выше самого высокого дерева ставить пилу бессмысленно: древесины будет 0.

3. Алгоритм

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

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

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

Пусть f(h) — количество древесины, которое получится при высоте пилы h.

Тогда:

• при увеличении h значение f(h) не возрастает;
• значит, все подходящие высоты образуют некоторый префикс: 0, 1, 2, ..., ans, а дальше идут только неподходящие.

Именно такую границу между "подходит" и "не подходит" удобно искать двоичным поиском.

Что делает алгоритм:

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

В итоге двоичный поиск найдёт максимальное значение h, для которого древесины не меньше M.

5. Сложность

На каждой итерации двоичного поиска мы за O(n) пересчитываем количество древесины.

Количество итераций двоичного поиска равно O(log max(a)).

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

• O(n log max(a))

Память:

• O(n) на хранение массива высот.

6. Код на C++17

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

using namespace std;

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

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

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

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

        long long wood = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] > mid) {
                wood += a[i] - mid;
            }
        }

        if (wood >= M) {
            answer = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

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

7. Код на Python 3

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

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

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

    wood = 0
    for x in a:
        if x > mid:
            wood += x - mid

    if wood >= M:
        answer = mid
        left = mid + 1
    else:
        right = mid - 1

print(answer)