Бинпоиск по ответу с жадной проверкой за O(n) — задача «Coffee and Coursework» РАЗБОР

Бинпоиск по ответу — одна из тех техник, после освоения которой десятки «средних» задач Div.2 C–D внезапно становятся понятными. Идея простая: вместо того чтобы искать сам ответ конструктивно, мы перебираем его, но не линейно, а половинным делением — и на каждом шаге только проверяем, достижим ли этот кандидат.

Техника работает, когда выполнены два условия:

1. Монотонность: если кандидат $d$ достижим, то все $d' > d$ тоже достижимы (или наоборот — если все $d' < d$).
2. Быстрая проверка: для фиксированного $d$ функцию «достижим или нет?» можно посчитать за $O(n)$ или $O(n \log n)$.

Эта задача — эталонный пример для освоения техники. Монотонность прямолинейная, проверка жадная и за линейное время, а в условии явно присутствует случай «ответа не существует» — что позволяет заодно разобрать типичную ловушку «забыл про $-1$».

---

Что дано

Есть $n$ кружек кофе. Кружка $i$ содержит $a_i$ единиц кофеина. Участник садится писать работу и планирует выпивать кружки днями. В один день можно выпить сколько угодно кружек (в том числе ноль).

Механика одного дня. В дне участник выбирает некоторое подмножество ещё не выпитых кружек и пьёт их в произвольном порядке. Если в этот день он выпил $k$ кружек с кофеином $c_1, c_2, \ldots, c_k$ именно в таком порядке, то страниц в этот день он напишет:

$$\max(0, c_1 - 0) + \max(0, c_2 - 1) + \ldots + \max(0, c_k - (k-1))$$

То есть первая кружка дня даёт полный кофеин, вторая теряет 1, третья — 2, и так далее. Если у кружки кофеин меньше «штрафа», страниц она даёт 0 (не может дать отрицательно).

За все дни суммарно нужно написать не менее $m$ страниц. Требуется найти минимальное количество дней $d$, за которое это возможно. Если невозможно даже при $d = n$ (каждая кружка в свой день) — вывести $-1$.

Ограничения

• $1 \leq n \leq 2 \cdot 10^5$ — количество кружек.
• $1 \leq m \leq 10^9$ — требуемое количество страниц.
• $1 \leq a_i \leq 10^9$ — кофеин каждой кружки.

Формат ввода

n m
a_1 a_2 ... a_n

Формат вывода

Одно целое число — минимальное $d$ или $-1$, если решения нет.

Примеры

Пример 1.

Вход:
5 8
2 3 1 1 2

Выход:
4

Пример 2.

Вход:
7 10
1 3 4 2 1 4 2

Выход:
2

Пример 3.

Вход:
5 15
5 5 5 5 5

Выход:
1

Пример 4.

Вход:
5 16
5 5 5 5 5

Выход:
2

Пример 5.

Вход:
5 26
5 5 5 5 5

Выход:
-1

Разберём первый пример руками

$n = 5$, $m = 8$, $a = [2, 3, 1, 1, 2]$.

Отсортируем кружки по убыванию кофеина: $[3, 2, 2, 1, 1]$.

Попробуем $d = 1$ (все за один день). Участник выпивает в порядке $3, 2, 2, 1, 1$. Страниц:

$$\max(0, 3) + \max(0, 2 - 1) + \max(0, 2 - 2) + \max(0, 1 - 3) + \max(0, 1 - 4) = 3 + 1 + 0 + 0 + 0 = 4.$$

$4 < 8$ — не хватает.

Попробуем $d = 2$. Нам нужно распределить 5 кружек на 2 дня. Оптимальная стратегия: в каждом дне первая по порядку кружка — самая «жирная» из оставшихся, вторая — следующая и так далее. Распределение:

Страниц: в 1-й день $3 + (2-1) + 0 = 4$; во 2-й $2 + 0 = 2$. Итого $6 < 8$.

Попробуем $d = 3$.

Страниц: $3 + 0 + 2 + 0 + 2 = 7 < 8$.

Попробуем $d = 4$.

Страниц: $3 + 0 + 2 + 2 + 1 = 8 \geq 8$ ✓.

Ответ — $4$ дня.

Интуиция, которую мы уже увидели. При раскладке по дням выгоднее сначала распределить по "первой позиции" в каждом дне кружки с наибольшим кофеином, потом — по "второй", и так далее. Это максимизирует страницы, потому что большие $a_i$ получают маленькие штрафы. И вторая вещь: функция «страниц за $d$ дней» монотонно не убывает по $d$ — добавили ещё один день, стало не хуже.

Осталось эти два наблюдения формализовать и использовать в бинпоиске.

---

Идея решения: бинпоиск по количеству дней

Алгоритм в одну фразу.

Выполняем бинпоиск по ответу $d$: ищем минимальное $d \in [1, n]$, для которого проверка $\text{check}(d) = \text{true}$. Проверка за $O(n)$ реализует жадную раскладку, описанную выше, и сравнивает сумму страниц с $m$.

Почему работает монотонность

Утверждение: если за $d$ дней можно написать $\geq m$ страниц, то за $d+1$ дней тоже можно.

Доказательство (конструктивное). Возьмём оптимальную раскладку на $d$ дней, дающую $\geq m$ страниц. Добавим $(d+1)$-й пустой день и не выпьем в нём ни одной кружки. Количество страниц не изменилось (новый день даёт 0), значит и при $d+1$ днях $\geq m$ тоже достижимо. ∎

Следовательно, множество допустимых $d$ — это непрерывный суффикс вида $[d^*, n] \cup \{\text{-1, если } d^* > n\}$. На таком множестве бинпоиск работает напрямую.

Границы бинпоиска: $\text{lo} = 1$, $\text{hi} = n$. Если $\text{check}(n) = \text{false}$ — ответ $-1$. Иначе бинпоиск находит минимальное $d$ с $\text{check}(d) = \text{true}$.

Почему работает жадная проверка

Для фиксированного $d$ утверждение: оптимальная раскладка — та, где кружки отсортированы по убыванию кофеина, и кружка номер $i$ (0-индексация после сортировки) идёт в день $i \bmod d$ на позицию $\lfloor i / d \rfloor$ в этом дне.

Другими словами: сначала раскладываем $d$ кружек с самым большим кофеином — по одной в каждый день на «первую позицию» (штраф 0). Потом следующие $d$ кружек — на «вторую позицию» в каждом дне (штраф 1). И так далее.

Почему это оптимально (exchange argument). Предположим, существует раскладка лучше нашей. Значит, в ней какая-то кружка $x$ с бо́льшим $a_x$ стоит на более поздней позиции внутри дня (с бо́льшим штрафом), чем какая-то кружка $y$ с меньшим $a_y$ на более ранней позиции.

Поменяем их местами. Штрафы у позиций не меняются — меняются только кружки, стоящие на них. Было:

• кружка $x$ на позиции со штрафом $p_x$: вклад $\max(0, a_x - p_x)$.
• кружка $y$ на позиции со штрафом $p_y$, причём $p_y < p_x$: вклад $\max(0, a_y - p_y)$.

Станет:

• кружка $x$ на позиции со штрафом $p_y$: вклад $\max(0, a_x - p_y)$.
• кружка $y$ на позиции со штрафом $p_x$: вклад $\max(0, a_y - p_x)$.

Разность «после − до»:

$$[\max(0, a_x - p_y) + \max(0, a_y - p_x)] - [\max(0, a_x - p_x) + \max(0, a_y - p_y)].$$

Это выражение $\geq 0$ для $a_x \geq a_y$ и $p_y \leq p_x$ (легко проверить перебором знаков слагаемых — свойство «монотонной парной рокировки»). То есть swap не ухудшает результат. Применив все такие свопы, приходим к нашей жадной раскладке. Значит, она не хуже любой другой. ∎

Как выражается штраф позиции

Кружка номер $i$ (0-индексация, в отсортированном по убыванию массиве) идёт в день $i \bmod d$, это её позиция $\lfloor i / d \rfloor$-я в дне (тоже 0-индексация). Штраф равен самой позиции. То есть вклад кружки $i$ в сумму страниц:

$$\text{contribution}(i, d) = \max(0, a_i - \lfloor i / d \rfloor).$$

И проверка за один проход по массиву:

$$\text{check}(d) = \left(\sum_{i=0}^{n-1} \max(0, a_i - \lfloor i/d \rfloor)\right) \geq m.$$

---

Решение: псевдокод

прочитать n, m, массив a длины n
отсортировать a по убыванию

функция check(d):
    total ← 0
    для i от 0 до n-1:
        penalty ← i // d
        total ← total + max(0, a[i] - penalty)
    вернуть total ≥ m

если не check(n):
    вывести -1 и выйти

# иначе — бинпоиск по d в [1, n], ищем минимальное с check(d) = true
lo ← 1
hi ← n
пока lo < hi:
    mid ← (lo + hi) // 2
    если check(mid):
        hi ← mid
    иначе:
        lo ← mid + 1
вывести lo

Сложность одной проверки — $O(n)$. Бинпоисков — $O(\log n)$. Итог: $O(n \log n)$ с учётом сортировки.

---

Код решения

Комментарии по реализации.

• Тип для сумм. $\sum a_i$ достигает $n \cdot \max a_i = 2 \cdot 10^{14}$, что превышает int32. В C++ обязателен long long для m, a[i] и total. В Python int автоматически большой — переполнения нет.
• Целочисленное деление. В Python — //, не /: оператор / даёт float. В бинпоиске (lo + hi) // 2 обязательно. В C++ используем mid = lo + (hi - lo) / 2 — каноничная безопасная форма без риска переполнения; для $n \le 2 \cdot 10^5$ можно и (lo + hi) / 2, но привычка окупается на больших границах.
• Сортировка по убыванию. Python — a.sort(reverse=True). C++ — sort(a.begin(), a.end(), greater<long long>()) напрямую, без rbegin/rend.
• Быстрый ввод. Python — sys.stdin.buffer.read().split() быстрее input() в цикле на больших $n$.
• Ранний выход из check (break, если value ≤ penalty) допустим, когда массив строго отсортирован по убыванию: дальше штрафы только растут, а значения только падают. Оставлено без раннего выхода для прозрачности — оба варианта в комментариях кода.

---

Проверим на всех примерах из условия

Ниже — отсортированные массивы и прогон check(d) для ключевых $d$ около ответа. Таблица для каждого примера показывает штраф $i / d$ и вклад кружки $i$.

Пример 1: $n=5, m=8, a=[2,3,1,1,2]$ → отсортированно $[3,2,2,1,1]$

$\text{check}(3)$: штрафы $0,0,0,1,1$. Вклады $3,2,2,0,0$. Сумма $7 < 8$. $\text{check}(4)$: штрафы $0,0,0,0,1$. Вклады $3,2,2,1,0$. Сумма $\mathbf{8 \geq 8}$ ✓.

Бинпоиск: $\text{lo}=1, \text{hi}=5$. $\text{mid}=3$, false → $\text{lo}=4$. $\text{mid}=4$, true → $\text{hi}=4$. $\text{lo}=\text{hi}=4$. Ответ: 4 ✓.

Пример 2: $n=7, m=10, a=[1,3,4,2,1,4,2]$ → отсортированно $[4,4,3,2,2,1,1]$

$\text{check}(1)$: штрафы $0,1,2,3,4,5,6$. Вклады $4,3,1,0,0,0,0$. Сумма $8 < 10$. $\text{check}(2)$: штрафы $0,0,1,1,2,2,3$. Вклады $4,4,2,1,0,0,0$. Сумма $\mathbf{11 \geq 10}$ ✓.

Бинпоиск: $\text{lo}=1, \text{hi}=7$. $\text{mid}=4$, надо проверить: штрафы $0,0,0,0,1,1,1$, вклады $4,4,3,2,1,0,0$, сумма $14 \geq 10$, true → $\text{hi}=4$. $\text{mid}=2$, true → $\text{hi}=2$. $\text{mid}=1$, false → $\text{lo}=2$. Ответ: 2 ✓.

Пример 3: $n=5, m=15, a=[5,5,5,5,5]$

$\text{check}(1)$: штрафы $0,1,2,3,4$. Вклады $5,4,3,2,1$. Сумма $\mathbf{15 \geq 15}$ ✓.

Бинпоиск стартует с $\text{lo}=\text{hi}=1$ почти сразу: $\text{mid}=3$, true → $\text{hi}=3$. $\text{mid}=2$, true (сумма $5+5+4+4+3=21$). $\text{mid}=1$, true. Ответ: 1 ✓.

Пример 4: $n=5, m=16, a=[5,5,5,5,5]$

$\text{check}(1)$: сумма $5+4+3+2+1=15 < 16$. $\text{check}(2)$: штрафы $0,0,1,1,2$. Вклады $5,5,4,4,3$. Сумма $\mathbf{21 \geq 16}$ ✓.

Бинпоиск даёт минимальное $d=2$. Ответ: 2 ✓.

Пример 5: $n=5, m=26, a=[5,5,5,5,5]$

$\text{check}(n) = \text{check}(5)$: штрафы $0,0,0,0,0$ (все кружки — первые в своих днях). Вклады $5+5+5+5+5=25 < 26$. Проверка не проходит → Ответ: $-1$ ✓.

Все 5 примеров дают эталонные ответы. Код корректен.

---

Крайние случаи

1. $n = 1$

Бинпоиск в диапазоне $[1, 1]$. check(1): штраф $0$, вклад $a_0 \geq m$? Если да — ответ $1$, иначе — $-1$. Код обрабатывает корректно.

2. Все $a_i$ одинаковые

Массив уже «отсортирован». Суммарный максимум страниц при $d = n$ равен $n \cdot a_0$. Если $m > n \cdot a_0$ — $-1$. Иначе бинпоиск находит минимальное $d$.

3. $m = 1$

Всегда достижимо за $d = 1$, если $a_0 \geq 1$ (а по ограничениям $a_i \geq 1$, значит всегда). Ответ $1$ без экзотики.

4. Максимальные значения

$n = 2 \cdot 10^5$, $a_i = 10^9$, $m = 10^9$. Промежуточная сумма в check — до $n \cdot 10^9 = 2 \cdot 10^{14}$. В C++ — long long (иначе переполнение int). В Python — автоматически.

5. Единственный $d$, где проверка падает

Теоретически бинпоиск может в какой-то момент «попасть» в $d$, где check(d) ложная, но соседние истинные. Не случится — из-за монотонности множество true — это суффикс. Если check(d) false, то и все меньшие $d$ false.

---

Типичные ошибки

1. Забыть про $-1$. Бинпоиск по $[1, n]$ всегда вернёт какое-то $d$. Без предварительной проверки check(n) код выведет неверный ответ на тестах, где задача неразрешима (пример 5).
2. int вместо long long в C++. Сумма страниц до $2 \cdot 10^{14}$ — int переполняется. После переполнения total становится отрицательным, и check возвращает false там, где должно быть true. WA на больших тестах.
3. Сортировка по возрастанию вместо убывания. Жадная раскладка требует, чтобы большие $a_i$ шли на малые штрафы. С обратной сортировкой всё работает «в зеркале» и даёт неправильный ответ.
4. Неверный размер штрафа. Штраф — $\lfloor i / d \rfloor$ (целочисленное деление), а не $i / d$ (вещественное) и не $i \bmod d$. / в Python 3 — это float-деление; писать //. В C++ для int / уже целочисленное, но важно не путать с остатком %.
5. Границы бинпоиска [0, n] вместо [1, n]. При $d = 0$ check делит на ноль. Нижняя граница должна быть $\text{lo} = 1$.
6. Ранний выход в check при нестрогом убывании. Если два a_i равны, строгое неравенство a[i] <= penalty в условии break может сработать раньше времени. Если всё же использовать ранний выход — условие a[i] < penalty (строгое) или a[i] - penalty <= 0.
7. Интерпретация «раскладки по дням» как день = i / d, позиция = i % d. Это тоже валидная раскладка, но для неё штраф позиции — i % d, а вклад — max(0, a[i] - (i % d)). Алгоритм остаётся корректным, но с другой формулой. Важно не перепутать / и %: раскладка, в которой день = i % d и позиция = i / d, даёт тот же ответ по сумме, но через другое «расписание».

---

Анализ сложности

• Сортировка: $O(n \log n)$.
• Бинпоиск: $O(\log n)$ итераций.
• Одна проверка: $O(n)$ проход по массиву.
• Итог: $O(n \log n)$ по времени, $O(n)$ по памяти (массив $a$).

При $n = 2 \cdot 10^5$ — это $\sim 3.4 \cdot 10^6$ операций, укладывается в типичный лимит 1–2 секунды с большим запасом.

---

Что ещё полезно потренировать

Задачи на ту же идею (бинпоиск по ответу с жадной или симуляционной проверкой). Все — с возраст-нейтральных платформ.

• Codeforces 1118D2 Div.3 (та же самая задача в «hard version» контеста, формулировка чуть развёрнутее) — если хочется закрепить именно этот паттерн.
• Codeforces Div.2 C–D уровня 1400–1600 с тегом binary search и greedy: типичные формулировки «найти минимальное $k$, такое что...» с быстрой жадной проверкой за $O(n)$ или $O(n \log n)$.
• acmp.ru, раздел «Бинарный поиск»: классические задачи уровня $1200$–$1700$, много чистых формулировок монотонной проверки (например, «разместить $k$ коров максимально далеко друг от друга по $n$ стойлам»).
• Яндекс Контест: архивы «Алгоритмы и структуры данных» содержат классические задачи на бинпоиск по ответу с различными типами проверок.

Для следующего шага — попробовать задачу, где проверка уже не чисто жадная, а требует небольшой симуляции или DP. Типичный пример — «минимальная длина подмассива с заданным свойством» через бинпоиск по длине + двухуказательная проверка.

---

Итого

• Идея: бинпоиск по минимальному количеству дней $d$ с проверкой за $O(n)$.
• Монотонность: если достижимо за $d$, то и за $d+1$ (добавили пустой день).
• Жадная проверка: сортировка по убыванию, кружка номер $i$ идёт в день $i \bmod d$, позиция $\lfloor i/d \rfloor$. Вклад — $\max(0, a_i - \lfloor i/d \rfloor)$.
• Крайний случай $-1$: проверить check(n) до бинпоиска. Без этой проверки алгоритм всегда выдаст валидное $d$, даже если задача неразрешима.
• Переполнение: long long в C++ для total (до $2 \cdot 10^{14}$).
• Сложность: $O(n \log n)$ по времени, $O(n)$ по памяти.