Семь задач на поиск по ответу

Схема поиска по ответу описана отдельно. Здесь — семь конкретных задач. Смысл не в самих условиях, а в том, чтобы натренировать шаг «придумать предикат»: именно на нём задачи и проигрываются.

Для каждой указано три вещи: что бинарим, как проверяем, где границы.

1. Коровы в стойла

На прямой стоят $n$ стойл с координатами $x_i$. Нужно расставить $k$ коров так, чтобы минимальное расстояние между соседними было максимальным.

Формулировка «максимизировать минимум» — самая надёжная примета поиска по ответу.

Бинарим по расстоянию $d$. Предикат: «можно расставить $k$ коров, чтобы все попарные расстояния были не меньше $d$». Проверка жадная — ставим первую корову в самое левое стойло и дальше каждую следующую в первое подходящее:

bool fits(const vector<long long>& x, int k, long long d) {
    int count = 1;
    long long last = x[0];
    for (size_t i = 1; i < x.size(); i++)
        if (x[i] - last >= d) { count++; last = x[i]; }
    return count >= k;
}

Жадность корректна: если корову можно поставить сейчас, откладывать её невыгодно — правее места только меньше.

Границы: $l = 0$ (всегда можно), $r = x_{n-1} - x_0 + 1$ (заведомо нельзя, если коров хотя бы две). Ответ — в l.

2. Провода

Есть $n$ кусков провода длиной $a_i$. Нужно нарезать хотя бы $k$ кусков одинаковой длины, как можно более длинных.

Бинарим по длине куска $d$. Проверка в одну строку: из провода длины $a_i$ получается $\lfloor a_i / d \rfloor$ кусков.

long long total = 0;
for (long long length : a) total += length / d;
return total >= k;

Границы: $l = 0$, $r = \max a_i + 1$. Ответ в l. Отдельно обработайте случай, когда ответ нулевой, — обычно требуется вывести $0$.

Ловушка: если длины вещественные (метры с сантиметрами), домножьте на $100$ и работайте в целых. Вещественный поиск здесь заведомо хуже.

3. Встреча в одной точке

$n$ человек стоят в точках $x_i$ и двигаются со скоростями $v_i$. За какое минимальное время все смогут собраться в одной точке?

Бинарим по времени $t$. За время $t$ человек $i$ достигает любой точки отрезка $[x_i - v_i t,\; x_i + v_i t]$. Все встретятся тогда и только тогда, когда у этих отрезков есть общая точка.

Пересечение отрезков — максимум левых концов против минимума правых:

double lo = -1e18, hi = 1e18;
for (int i = 0; i < n; i++) {
    lo = max(lo, x[i] - v[i] * t);
    hi = min(hi, x[i] + v[i] * t);
}
return lo <= hi;

Монотонность очевидна: с ростом $t$ отрезки только расширяются, и однажды пересёкшись, разойтись уже не могут.

Здесь ответ вещественный — значит, вещественный поиск с фиксированным числом итераций.

4. Два принтера

Первый принтер печатает лист за $x$ минут, второй за $y$. Нужно напечатать $n$ листов. За какое минимальное время?

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

Бинарим по времени $t$. За $t$ минут первый напечатает $\lfloor t/x \rfloor$, второй $\lfloor t/y \rfloor$:

return t / x + t / y >= n;

Границы: $l = 0$, $r = n \cdot \min(x, y)$ — этого хватит гарантированно. Ответ в r, потому что минимизируем.

Это общий приём: вместо вывода формулы напишите проверку. Проверка почти всегда очевидна, а формула — нет. Логарифм сверху обычно можно себе позволить.

5. Воздушные шарики

$n$ помощников надувают шарики. Помощник $i$ работает $t_i$ минут, надувая $z_i$ шариков, потом отдыхает $y_i$ минут, и так по кругу. Нужно $m$ шариков. За какое минимальное время?

Бинарим по времени $T$. Для каждого помощника считаем, сколько он успеет: полных циклов $\lfloor T / (t_i + y_i) \rfloor$, плюс остаток, который надо аккуратно поделить между работой и отдыхом:

long long cycle = t[i] + y[i];
long long full = T / cycle;
long long rest = min(T % cycle, t[i]);   // в остатке он работает не дольше t[i]
total += full * z[i] + rest * z[i] / t[i];

Два подвоха. Первый — min в остатке: если остаток попал на отдых, лишнего не начислится. Второй — задача обычно просит вывести точное распределение, кто сколько надул, а за время $T$ помощники успевают больше нужного. Лишнее приходится отрезать отдельным жадным проходом. На этом и падают решения: время найдено верно, а восстановление ответа неверное.

6. Выборы

За кандидата $i$ голосует $a_i$ человек, и подкуп одного избирателя стоит одну монету. Для каждого кандидата надо сказать, сколько монет нужно, чтобы он победил (у него строго больше голосов, чем у любого другого).

Здесь поиск по ответу вложен во внешний цикл, и наивно получается медленно.

Фиксируем кандидата $i$ и бинарим по $X$ — числу голосов, с которым он победит; заведомо $X > a_i$. Проверка: у всех остальных должно стать меньше $X$, значит у кандидата $j$ с $a_j \ge X$ нужно отобрать $a_j - X + 1$ голосов. Сумма таких изъятий — обязательные траты $S$. Если $S \le X - a_i$, бюджета хватает, и недостающие голоса докупаются у кого угодно.

Прямая проверка — $O(n)$, итого $O(n^2 \log n)$ на всех кандидатов. Слишком медленно при $n = 10^5$.

Ускорение: отсортируем $a$ и посчитаем суффиксные суммы. Тогда те, у кого $a_j \ge X$, — это суффикс отсортированного массива, его начало ищется lower_bound за логарифм, а сумма изъятий берётся готовой:

$$S = \text{suffixSum}(g) - (X - 1) \cdot (n - g)$$

где $g$ — первый индекс с $a_g \ge X$. Проверка стала $O(\log n)$, всё решение — $O(n \log^2 n)$.

Самого кандидата $i$ из суффикса исключать не нужно: раз $X > a_i$, он в него не попадает. Это тот случай, когда проверка формулы перебором на маленьких данных экономит час отладки.

Это типичный второй этап таких задач: сначала придумать проверку, потом ускорить её предподсчётом. Придумывать сразу быструю проверку почти никогда не нужно.

7. Дипломы

Нужно напечатать $n$ дипломов прямоугольниками $w \times h$ на квадратном листе стороны $s$. Найдите минимальное $s$.

Бинарим по стороне. На лист стороны $s$ помещается $\lfloor s/w \rfloor \cdot \lfloor s/h \rfloor$ дипломов:

return (s / w) * (s / h) >= n;

Единственная сложность — переполнение. При $s$ до $10^{18}$ произведение двух частных не помещается никуда. Спасает ранний выход: если первый множитель уже не меньше $n$, ответ положителен без умножения.

long long first = s / w, second = s / h;
if (first == 0 || second == 0) return false;
if (first >= n || second >= n) return true;
return first * second >= n;   // оба меньше n — произведение не переполнится

Что общего

Во всех семи задачах порядок действий один:

1. Назвать величину, которую бинарим, — это всегда ответ или его часть, а не индекс.
2. Записать предикат словами и убедиться, что он монотонен.
3. Найти границы, где предикат заведомо ложен и заведомо истинен, — с запасом.
4. Написать проверку максимально прямолинейно.
5. Только если не проходит по времени — ускорять проверку.

Шаг 2 пропускают чаще всего, и именно он ломает решение на закрытых тестах.