1. Идея

Нужно найти наименьшее целое d >= 1, для которого

ceil(a_1 / d) + ceil(a_2 / d) + ... + ceil(a_n / d) <= K.

Перебирать все d подряд нельзя: a_i могут быть до 10^9, значит и ответ тоже может быть очень большим.

Ключевая идея — применить двоичный поиск по ответу.

Если фиксировать d, то можно посчитать сумму S(d). При увеличении d каждое значение ceil(a_i / d) не увеличивается, а значит и вся сумма S(d) тоже не увеличивается. Получается монотонность:

• если для некоторого d условие S(d) <= K выполняется,
• то для любого большего d оно тоже будет выполняться.

Значит, существует граница: слева d ещё плохие, справа уже хорошие. Такую границу удобно искать двоичным поиском.

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

Наблюдение 1. Как считать ceil(a_i / d)

Для целых чисел удобно использовать формулу:

ceil(a_i / d) = (a_i + d - 1) // d

Именно так это и реализовано в коде.

Наблюдение 2. Почему ответ точно существует

По условию K >= n.

Если взять d = max(a_i), то для каждого a_i выполнится:

• a_i <= d,
• значит ceil(a_i / d) = 1.

Тогда

S(d) = 1 + 1 + ... + 1 = n.

А так как n <= K, условие S(d) <= K точно выполнено.

Значит, ответ существует, и его можно искать на отрезке от 1 до max(a).

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

Пусть d1 < d2. Тогда делитель d2 больше, поэтому:

ceil(a_i / d2) <= ceil(a_i / d1) для каждого i.

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

S(d2) <= S(d1).

Это и делает задачу задачей на поиск минимального подходящего значения по монотонному признаку.

Наблюдение 4. Ранний выход при подсчёте

Когда считаем сумму S(d), нет смысла досчитывать её до конца, если она уже стала больше K.

Как только sum > K, можно сразу сказать, что текущее d не подходит.

Это не меняет асимптотику, но делает решение быстрее на практике.

3. Алгоритм

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

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

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

1. Проверка good(d) действительно определяет, подходит ли d

Для фиксированного d мы считаем сумму

S(d) = sum of ceil(a_i / d).

Если S(d) <= K, то по условию задачи такой шаг округления подходит. Если S(d) > K, то не подходит.

Значит, проверка верно отвечает на вопрос для каждого d.

2. Множество подходящих d имеет вид от некоторого места до конца

Как уже отмечалось, при увеличении d каждое значение ceil(a_i / d) не возрастает. Значит, и сумма S(d) не возрастает.

Отсюда:

• если некоторое d подходит,
• то любое большее d тоже подходит.

Следовательно, все значения d делятся на две части:

• сначала неподходящие,
• потом подходящие.

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

3. Границы поиска выбраны правильно

• left = 1 — минимально возможный шаг.
• right = max(a) — точно подходящее значение, потому что тогда каждая дробь округляется вверх к 1, и суммарно получаем n <= K.

Значит, искомый ответ лежит в диапазоне [1, max(a)].

4. Двоичный поиск находит именно минимальный подходящий d

На каждом шаге берётся середина mid.

• Если mid подходит, то ответ находится в диапазоне [left, mid], поэтому можно отбросить правую часть и сделать right = mid.
• Если mid не подходит, то ответ строго больше mid, поэтому можно сделать left = mid + 1.

Так как диапазон каждый раз уменьшается, процесс закончится. Когда left == right, остаётся ровно одно значение, и по свойству двоичного поиска это минимальное подходящее d.

Следовательно, алгоритм корректен.

5. Сложность

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

• Одна проверка good(d) работает за 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 K;
    cin >> n >> K;

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

    auto good = [&](long long d) {
        long long sum = 0;
        for (int i = 0; i < n; ++i) {
            sum += (a[i] + d - 1) / d;
            if (sum > K) {
                return false;
            }
        }
        return sum <= K;
    };

    long long left = 1, right = mx;
    while (left < right) {
        long long mid = left + (right - left) / 2;
        if (good(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 = 1
right = max(a)

while left < right:
    mid = (left + right) // 2
    total = 0
    for x in a:
        total += (x + mid - 1) // mid
        if total > K:
            break

    if total <= K:
        right = mid
    else:
        left = mid + 1

print(left)