Стратегия победы: бинпоиск по ответу — траектория 1200 → 1500 → 2000 СТРАТЕГИЯ

«Бинпоиск по ответу» — техника, у которой каркас один (см. серию «Алгоритмические основы» и тему про инвариант). Растущая сложность задач — это не сложность шаблона, а сложность предиката can(x). На полосе CF 1200 проверка укладывается в одну строку. На полосе 1500 — в жадный обход массива с обоснованием. На полосе 2000 — в нетривиальный подсчёт с участием сортировки и анализа сразу нескольких элементов.

Эта статья — траектория тренировки на бинпоиск по ответу. Берём три задачи разной полосы, для каждой подробно разбираем: как переформулировать условие, как сформулировать предикат, какие отсечения границ и какие особенности проверки.

---

Ядро техники

Базовая форма (см. соответствующую тему серии «Алгоритмические основы»):

lo, hi ← границы кандидатов
пока lo < hi:
    mid ← (lo + hi + 1) / 2          # для max-true
    или
    mid ← (lo + hi) / 2              # для min-true
    если can(mid):
        сдвигаем границу к mid
    иначе:
        сдвигаем границу от mid
вернуть lo  # = hi

Где can(mid) — бинарный предикат «достижим ли ответ mid». Содержательная часть техники — именно can.

---

Ступень 1 (~CF 1200): Aggressive Cows

Условие

Дано $n$ позиций на прямой $a_1 < a_2 < \ldots < a_n$ (все различны, целые, отсортированы). Нужно расставить $k$ объектов в эти позиции ($k \le n$) так, чтобы минимум попарных расстояний между расставленными объектами был максимален. Найти это максимальное минимальное расстояние.

Ограничения. $2 \le k \le n \le 10^5$, $0 \le a_i \le 10^9$.

Пример. $a = [1, 2, 4, 8, 9]$, $k = 3$. Возможные тройки и их минимумы попарных расстояний:

• $\{1, 4, 8\}$: $\min(3, 4, 7) = 3$.
• $\{1, 4, 9\}$: $\min(3, 5, 8) = 3$.
• $\{2, 4, 9\}$: $\min(2, 5, 7) = 2$.
• $\{1, 8, 9\}$: $\min(7, 1, 8) = 1$.
• … и т.д.

Ответ — $3$.

Выбор инварианта

Переформулировка: «при фиксированном $d$, можно ли расставить $k$ объектов так, чтобы каждая пара соседних была на расстоянии $\ge d$?». Это can(d).

Монотонность: при $d_1 < d_2$ — если $d_2$ достижимо, то $d_1$ тем более достижимо (то же расположение). Точка перехода единственная. Форма (A) max-true, ищем максимальное $d$ с can(d) = true.

Границы: $\textit{lo} = 1$ (хотя $d = 0$ всегда достижимо тривиально, нам важен «непрерывный» инвариант — отсечём вырожденный $d = 0$ и стартуем с $1$). $\textit{hi} = a_n - a_1$ (больше максимально возможного расстояния между крайними точками).

Проверка

Жадная: ставим первый объект в $a_1$, далее идём по позициям и ставим следующий объект в первую позицию, отстоящую от последнего поставленного на $\ge d$. В конце сравниваем число поставленных с $k$.

cnt ← 1
last ← a[0]
для x из a[1..]:
    если x - last ≥ d:
        cnt ← cnt + 1
        last ← x
вернуть cnt ≥ k

Почему жадно — оптимально? Допустим, существует расстановка из $k$ объектов с расстояниями $\ge d$, где первый объект стоит не в $a_1$. Сдвинем его в $a_1$ — расстояния от первого до второго не уменьшатся (потому что мы сдвинули влево). Аналогично для второго: если он стоит правее «первой позиции с расстоянием $\ge d$» — сдвинем влево; расстояние ко второму увеличится, расстояние к третьему не уменьшится. По индукции — жадный выбор всегда даёт ровно столько же или больше объектов, чем любая другая расстановка.

Код

Что характерно для ступени 1

• Проверка — одна линейная пробежка. Никакой структуры данных, просто счётчик.
• Жадность очевидна. Доказательство exchange argument умещается в одну фразу.
• Сложность. $O(n \log n)$ на сортировку + $O(n \log a_{\max})$ на бинпоиск. Всё дешёво.

---

Ступень 2 (~CF 1500): минимизация времени с проверкой по сумме делений

Условие

В сервисе $n$ операторов с темпами $t_1, t_2, \ldots, t_n$ — оператор $i$ обрабатывает один запрос за $t_i$ секунд (последовательно). В очереди $m$ запросов. Найти минимальное целое время $T$, за которое все $m$ запросов будут обработаны, при условии, что операторы работают параллельно и каждый берёт следующий запрос сразу, как освободится.

Ограничения. $1 \le n \le 10^5$, $1 \le m \le 10^9$, $1 \le t_i \le 10^9$.

Пример. $t = [1, 2, 3]$, $m = 5$. За время $T$ оператор $i$ обработает $\lfloor T / t_i \rfloor$ запросов:

• $T = 2$: $2 + 1 + 0 = 3$ < 5 — нет.
• $T = 3$: $3 + 1 + 1 = 5$ ≥ 5 — да.

Ответ — $3$.

Выбор инварианта

Переформулировка: «при фиксированном $T$, можно ли обработать $m$ запросов?». Это can(T) = (sum(T // t_i) >= m).

Монотонность: при $T_1 < T_2$ — каждое слагаемое не уменьшается, сумма не уменьшается. Если can(T_1), то can(T_2). Форма (B) min-true.

Границы: $\textit{lo} = 1$, $\textit{hi} = \min(t_i) \cdot m$ (один самый быстрый оператор сам справится за это время).

Проверка

sum ← 0
для t_i из t:
    sum ← sum + T // t_i
    если sum ≥ m:
        вернуть истина
вернуть истина если sum ≥ m, иначе ложь

Простая, но требует внимания: $T \cdot m$ может переполнять int при $T, m \sim 10^{18}$. В этой задаче ограничения мягче, но привычка использовать long long — полезна.

Код

Что характерно для ступени 2

• Проверка — сумма по элементам, но требует осторожности с переполнением. $T / t_i$ может суммироваться в большое число, обязательно long long.
• Граница $\textit{hi}$ — продуктовая. Не «удвоить $\textit{lo}$, пока не достигнет», а сразу min(t) * m — упирается в самого быстрого оператора. Тонкое наблюдение, отличающее ступень 1 от ступени 2.
• Сложность. $O(n \log (\min(t) \cdot m))$ — лог от $\sim 10^{18}$ это $\sim 60$, итого $\sim 6 \cdot 10^6$ операций при $n = 10^5$.

---

Ступень 3 (~CF 2000): максимизация медианы через k операций

Условие

Дан массив $a$ из $n$ положительных целых чисел, $n$ нечётное. Дано целое $k \ge 0$ — количество доступных операций. За одну операцию можно увеличить любой один элемент массива на $1$. Найти максимальное возможное значение медианы массива (медиана — элемент на позиции $\lceil n/2 \rceil$ в отсортированном порядке) после применения $\le k$ операций.

Ограничения. $1 \le n \le 2 \cdot 10^5$, $n$ нечётное, $0 \le k \le 10^9$, $1 \le a_i \le 10^9$.

Пример. $a = [1, 3, 5]$, $k = 2$. Медиана — второй элемент в отсортированном порядке. Чтобы максимизировать, увеличиваем средний элемент: $[1, 5, 5] \Rightarrow$ медиана $= 5$. (Можно перейти в $[1, 4, 5]$ за 1 операцию, в $[1, 5, 5]$ за 2 операции — медианы соответственно 4 и 5.) Ответ — $5$.

Пример 2. $a = [1, 3, 5, 7, 9]$, $k = 6$. Медиана — третий элемент в отсортированном порядке. Нужно поднять верхние три элемента: позиции в отсортированном — $5, 7, 9$. Чтобы медиана была $\ge x$, должно быть $\ge 3$ элементов $\ge x$. При $x = 9$: $5 \to 9$ (4 операции), $7 \to 9$ (2 операции), $9 \to 9$ (0) — итого $6$ операций, всё ровно. Ответ — $9$.

Выбор инварианта

Переформулировка: «при фиксированном $x$, можно ли за $\le k$ операций добиться, чтобы $\ge \lceil n/2 \rceil$ элементов было $\ge x$?». Это can(x).

Монотонность: при $x_1 < x_2$ — если для $x_2$ нужно столько-то операций, для $x_1$ нужно не больше (любое поднятие до $x_2$ покрывает поднятие до $x_1$). Если can(x_2), то can(x_1). Форма (A) max-true.

Границы: $\textit{lo} = \min a$ (любое уже достигнутое значение, не превышающее), $\textit{hi} = \max a + k$ (даже потратив все $k$ операций на один элемент, не получим больше).

Проверка — содержательная часть

Сколько операций минимально нужно, чтобы $\ge \lceil n/2 \rceil$ элементов было $\ge x$? Жадный ответ: отсортировать массив; верхнюю половину (включая медиану) — это позиции от $n - \lceil n/2 \rceil$ до $n - 1$ — поднять до $x$. Поднимать ниже-стоящие элементы бесполезно: они меньше, операций потратили бы больше.

half ← (n + 1) / 2
sorted_a ← отсортированный a
cost ← 0
для i от n - half до n - 1:
    если sorted_a[i] < x:
        cost ← cost + (x - sorted_a[i])
        если cost > k:
            вернуть ложь
вернуть истина

Почему именно верхняя половина — оптимально? Допустим, есть допустимый план, в котором мы подняли не верхнюю половину, а какие-то другие $\lceil n/2 \rceil$ элементов до $\ge x$. Тогда среди них есть хотя бы один элемент с индексом $< n - \lceil n/2 \rceil$ — он в отсортированном меньше каждого элемента из верхней половины. Заменим его в плане на любой нижний из «верхней половины, не достигший $x$»: стоимость замены не вырастет (новый элемент уже не меньше старого, до $x$ ему «ближе»). По цепочке таких замен — приходим к плану, поднимающему именно верхнюю половину. Доказано оптимальность жадного — exchange argument.

Сложность проверки: $O(\lceil n/2 \rceil)$ после однократной сортировки.

Применение шаблона

Сортируем массив один раз, потом запускаем бинпоиск. Это важно: если сортировать на каждой проверке, $O(n \log n \cdot \log R)$ — потенциально не пройдёт TL.

a ← отсортированный массив
lo, hi ← a[0], a[n-1] + k
пока lo < hi:
    mid ← (lo + hi + 1) / 2
    если can(mid):
        lo ← mid
    иначе:
        hi ← mid - 1
вернуть lo

Код

Что характерно для ступени 3

• Проверка — не одна формула, а жадный план + обоснование. Это уже не «сумма по элементам», а «оптимальная стратегия использования $k$ операций».
• Подготовка данных вне can. Сортировка один раз перед бинпоиском — важно для сложности. На ступени 1 сортировка тоже была, но тривиальная; здесь её роль — основа корректности жадного.
• Доказательство оптимальности — exchange argument на 2–3 строки. Без него жадный — догадка.
• Сложность. $O(n \log n + n \log (a_{\max} + k))$.

---

Сводная таблица

Сама форма цикла — одинаковая на всех трёх ступенях. Меняется только can. И именно can — фокус внимания при росте сложности.

---

Типичные ловушки по ступеням

Ступень 1. Зацикливание из-за неправильного округления mid (см. тему про бинпоиск по ответу). На массиве позиций — забыть отсортировать перед жадной проверкой.

Ступень 2. Переполнение при умножении $\textit{lo} \cdot m$ для границы $\textit{hi}$. Слишком тесный TL при $n = 10^5$ — нужно sys.stdin.buffer.read в Python, иначе ввод съест половину времени.

Ступень 3. Сортировать массив внутри can — $O(n \log n)$ на каждую проверку, итого $O(n \log n \cdot \log R)$ ≈ $5 \cdot 10^7$, потенциальный TL в Python. Поднимать неправильную половину массива (нижнюю, центральную, всю) — типичный WA до того, как обосновал, какую именно половину поднимать. Забыть, что $n$ нечётное и медиана — это позиция $\lceil n/2 \rceil$ (0-индексация: $\lfloor n/2 \rfloor$), а не середина в обычном смысле.

---

План тренировки

Если только знакомитесь с бинпоиском по ответу — порядок такой:

1. Прочесть тему «Бинпоиск по ответу: когда применять и как выбирать инвариант» (серия «Алгоритмические основы»). Освоить базовый шаблон, обе формы цикла и принцип монотонности.
2. Решить 2–3 задачи уровня ступени 1 — Aggressive Cows, распил досок (см. тему), минимизация $T$ с простой проверкой. Цель — научиться формулировать can за 5 минут от прочтения условия.
3. Перейти к ступени 2 — задачи, где граница $\textit{hi}$ требует продуктового рассуждения, или где проверка требует аккуратной арифметики (long long, ceil/floor).
4. Ступень 3 — задачи, где can сама нетривиальна: содержит жадный, требует exchange argument, или вообще DP внутри. На этой полосе техника бинпоиск по ответу перестаёт быть отдельной — она становится каркасом, в который вкладывается отдельный алгоритм.

Признак, что ступень освоена: при виде нового условия в соответствующей полосе CF — за 5 минут формулируете can, доказываете монотонность, выбираете границы. Дальше — техника.

---

Итого

• Каркас один: цикл бинпоиска по диапазону кандидатов с предикатом can(x).
• Растёт сложность can. От «сумма по массиву» до «жадный план с обоснованием через exchange argument». От $O(n)$ до $O(n)$ после $O(n \log n)$-подготовки.
• Растёт сложность выбора границ. От «$1$ и $a_n - a_1$» до «$\min(t) \cdot m$ как продуктовая оценка».
• Содержательная часть — не цикл, а can. Освоить технику — значит освоить не четырёхстрочный цикл, а сотни возможных способов записать can для разных задач.

После этой стратегии полезно вернуться к теме «Бинпоиск по ответу: когда применять и как выбирать инвариант» и пройти её ещё раз — многие тонкости станут понятнее именно после трёх практик.