1. Идея

Нужно найти максимальную целую длину куска L, такую что из всех рулонов можно получить как минимум k кусков длины L.

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

• из рулона длины a_i получится a_i // L кусков;
• всего кусков будет сумма a_i // L по всем рулонам.

Главная идея: использовать двоичный поиск по ответу.

Почему это возможно? Потому что если некоторая длина L подходит, то любая меньшая длина тоже подходит: чем короче куски, тем больше их можно нарезать. Значит, существует граница:

• все длины до некоторого значения подходят;
• все длины больше него — уже нет.

Такую границу удобно искать двоичным поиском.

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

Наблюдение 1. Как проверить конкретную длину

Для заданного L число кусков равно:

a_1 // L + a_2 // L + ... + a_n // L

Если эта сумма не меньше k, то длина L подходит.

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

Если длина L подходит, то любая длина меньше L тоже подходит.

Действительно, при уменьшении длины куска значение a_i // L не убывает, а значит и общее число кусков тоже не убывает.

Это и есть монотонность, необходимая для двоичного поиска.

Наблюдение 3. Границы поиска

• Минимальная разумная длина — 1.
• Максимальная длина не может быть больше самого длинного рулона, то есть max(a).

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

Наблюдение 4. Можно прерывать подсчёт раньше

Во время проверки длины L, если уже набрали pieces >= k, можно дальше не считать: нам достаточно знать, что длина подходит.

Это не меняет ответ, но ускоряет программу.

3. Алгоритм

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

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

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

Обозначим через f(L) количество кусков длины L, которые можно получить из всех рулонов:

f(L) = sum(a_i // L)

Нас интересуют такие L, для которых f(L) >= k.

Свойство монотонности

Если L1 < L2, то для любого рулона:

a_i // L1 >= a_i // L2

Значит:

f(L1) >= f(L2)

То есть при увеличении L значение f(L) не возрастает. Следовательно, множество подходящих значений L имеет вид:

1, 2, ..., ans

для некоторого максимального ans.

Что делает двоичный поиск

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

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

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

Почему answer будет правильным

Переменная answer обновляется только тогда, когда текущая длина mid подходит. Значит, в answer всегда хранится допустимая длина.

Так как после подходящего mid поиск продолжается вправо, алгоритм обязательно найдёт наибольшую подходящую длину.

Следовательно, после завершения цикла answer — это максимальная целая длина куска, при которой можно получить не меньше k кусков.

5. Сложность

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

• Одна проверка значения L требует 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];
        if (a[i] > mx) mx = a[i];
    }

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

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

        long long pieces = 0;
        for (int i = 0; i < n; i++) {
            pieces += a[i] / mid;
            if (pieces >= k) break;
        }

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

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

7. Код на Python 3

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

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

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

    for x in a:
        pieces += x // mid
        if pieces >= k:
            break

    if pieces >= k:
        answer = mid
        left = mid + 1
    else:
        right = mid - 1

print(answer)