Сегодня разбираем один из самых частотных приёмов - бинарный поиск по ответу. Если в условии есть «найдите минимальное/максимальное такое, что...», то с большой вероятностью это он.
Идея
Обычный бинпоиск ищет элемент в отсортированном массиве. Бинпоиск по ответу - про другое: мы ищем не элемент в массиве, а сам ответ в диапазоне возможных значений.
Ключевое наблюдение: часто прямую задачу «найди оптимальное значение» решать сложно, а обратную «подходит ли конкретное x?» - намного легче. Тогда мы просто перебираем x бинпоиском.
Работает это при монотонности. Пусть есть функция check(x), возвращающая true/false. Если она выглядит как FFFF...FTTT...T (сначала false, потом true) или TTTT...TFFF...F, то бинпоиском можно найти границу, где ответ меняется. Эта граница и есть ответ.
Если check(x) не монотонна - приём не работает, это первое, что нужно проверять.
Разберём на задаче
Дано n досок с длинами a[i] и число k. Нужно распилить доски на куски одинаковой целочисленной длины L так, чтобы кусков получилось хотя бы k. Найти максимальную L.
Из доски длины a[i] при длине куска L выйдет a[i] / L кусков (целочисленное деление).
Замечаем монотонность: чем меньше L, тем больше кусков. Если при некотором L набираем ≥ k кусков, то при любом меньшем - тем более. При большем L в какой-то момент кусков станет мало. Значит функция "можно ли набрать k кусков при длине L" монотонна: TTT...TFFF. Ищем последнюю L, где ещё T.
Функция check
Проверяет, хватает ли кусков при длине L:
bool check(int L, vector<int>& a, int k) {
if (L == 0) return true;
long long cnt = 0;
for (int x : a)
cnt += x / L;
return cnt >= k;
}Обратите внимание на long long - кусков может быть очень много, в int не влезет.
Сам бинпоиск
Ищем максимальную L, при которой check вернёт true:
int solve(vector<int>& a, int k) {
int lo = 1, hi = *max_element(a.begin(), a.end());
int ans = 0;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (check(mid, a, k)) {
ans = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return ans;
}Логика по шагам:
1. lo и hi - границы возможного ответа. Минимум 1, максимум - самая длинная доска.
2. Берём середину mid и спрашиваем check.
3. Подходит - запоминаем ответ и идём вправо (хотим L побольше).
4. Не подходит - идём влево.
5. Границы схлопнулись, в ans лежит максимальное подходящее L.
Важные моменты
mid считаем как lo + (hi - lo) / 2, а не (lo + hi) / 2 — при больших числах сумма переполнит int.
Если ищем минимальное подходящее значение (шаблон FFF...FTTT), логика зеркальная: при true сохраняем ответ и идём влево.
Всегда проверяйте крайние случаи: ответа вообще нет, весь диапазон подходит. Обычно баги появляются именно тут.
Вещественный бинпоиск
Если ответ дробный (например, в геометрии), вместо while крутим фиксированное число итераций:
double lo = 0, hi = 1e9;
for (int iter = 0; iter < 100; iter++) {
double mid = (lo + hi) / 2;
if (check(mid))
lo = mid;
else
hi = mid;
}
100 итераций дают точность порядка 1e9 / 2^100 - с запасом на любой eps.
Асимптотика
Один check работает за O(n), бинпоиск делает O(log(max_answer)) итераций. Итого O(n log(max_answer)).
Где применять
Максимизируйте минимум / минимизируйте максимум
Распределение по k группам
Задачи со временем («за какое минимальное время успеем»)
Геометрия с вещественным ответом
Любая задача, где проверить ответ проще, чем построить
Практика
Коровы в стойла
Delivery Dilemma
Aggressive cows
Find K-th Smallest Pair Distance
@postupashki_prog