Поиск по ответу

Бинарный поиск по массиву — частный случай. Общий выглядит так.

Есть функция check(x), которая для маленьких $x$ возвращает false, а начиная с какого-то момента — всегда true. Иначе говоря, воображаемый массив её значений выглядит как

0 0 0 0 0 1 1 1 1 1

Найти границу между нулями и единицами — это ровно тот же бинарный поиск, только вместо a[mid] вызывается check(mid).

long long l = -1, r = LIMIT;    // check(l) ложно, check(r) истинно
while (r - l > 1) {
    long long mid = l + (r - l) / 2;
    if (check(mid)) r = mid;
    else l = mid;
}
// r — наименьшее значение, при котором check истинно

Массива здесь нет вовсе. Есть только функция и обещание, что она монотонна.

Три приметы в условии

Задача решается поиском по ответу, когда сходятся три вещи:

1. Спрашивается «наименьшее $X$, при котором получится» или «наибольшее $X$, при котором ещё хватит».
2. Проверить конкретное $X$ легко, а найти его прямо — непонятно как.
3. Ответ монотонен: если при $X$ получилось, то при всех больших (или всех меньших) тоже.

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

Как выглядит check

Проверка почти всегда — жадный проход или формула.

Развезти ящики за $d$ дней машиной грузоподъёмности $X$. Грузим подряд, пока влезает; не влезло — новый день. Считаем дни, сравниваем с $d$.

bool check(long long capacity) {
    int days = 1;
    long long current = 0;
    for (long long weight : boxes) {
        if (weight > capacity) return false;   // не увезём вообще
        if (current + weight <= capacity) current += weight;
        else { days++; current = weight; }
    }
    return days <= d;
}

Нарезать $k$ кусков длины $L$ из имеющихся верёвок. Сумма $\lfloor l_i / L \rfloor$ сравнивается с $k$.

Успеют ли станки сделать $n$ деталей за $T$ минут. Сумма $\lfloor T / t_i \rfloor$ сравнивается с $n$.

Общее у всех трёх: проверка линейна, а перебор ответа стоил бы линии на каждое значение.

Границы поиска

Нижнюю границу берут не «ноль на всякий случай», а такую, при которой проверка осмысленна. В задаче про грузоподъёмность машина легче самого тяжёлого ящика не увезёт ничего, и жадный проход на таком значении либо соврёт, либо зациклится. Значит, нижняя фиктивная граница — «самый тяжёлый ящик минус один».

Верхнюю берут заведомо достаточной, но не «на всякий случай огромной»: чем шире промежуток, тем больше шагов, а при вычислениях внутри check большие числа ещё и переполняются.

Когда монотонность спрятана

Интереснее всего задачи, где монотонность есть, но не та, про которую спрашивают.

Минимум максимума. Даны неубывающий массив $A$ и невозрастающий $B$; нужно $k$, при котором $\max(A_k, B_k)$ минимален. Сам максимум по $k$ не монотонен — он сначала падает, потом растёт. Зато монотонна разность $A_k - B_k$: она не убывает. Бинарным поиском находим первое $k$, где $A_k \ge B_k$, и проверяем два соседних варианта.

Общий приём: если функция «падает, потом растёт», ищите монотонную величину, которая меняет знак в точке минимума.

Отношение. Максимизировать $\frac{\sum v_i}{\sum w_i}$ по подмножеству из $k$ элементов. Набор с отношением не меньше $\lambda$ существует тогда и только тогда, когда максимум суммы $v_i - \lambda w_i$ по $k$ элементам неотрицателен — а это просто «взять $k$ наибольших». Предикат монотонен по $\lambda$, и поиск работает.

Чётность. В отсортированном массиве все числа встречаются дважды, кроме одного. Само значение ничего не подсказывает, а вот позиции — да: до одинокого элемента пары стоят на местах $(1,2), (3,4), \ldots$, а после него сдвигаются. Предикат «пара с номером $t$ ещё не сдвинута» монотонен.