Бинарный поиск по ответу

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

#«Коровы в стойла»

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

Гарантируется, что $1 < k < n$.

Если решать задачу в лоб, то вообще неясно, что делать. Вместо этого нужно решим более простую задачу: предположим, что мы знаем это расстояние $x$, ближе которого коров ставить нельзя. Тогда сможем ли мы расставить самих коров?

Ответ — да, причём довольно просто: самую первую ставим в самое левое стойло, потому что это всегда выгодно. Следующие несколько стойл надо оставить пустыми, если они на расстоянии меньше $x$, а в самое левое стойло из оставшихся надо поставить вторую корову, и так далее.

Как это реализовать: надо идти слева направо по отсортированному массиву стойл, хранить координату последней коровы, и в зависимости от расстояния до предыдущей коровы либо пропускать стойло, либо ставить в него новую корову.

bool check(int x) {
    int cows = 1;
    int last_cow = coords[0];
    for (int c : coords) {
        if (c - last_cow >= x) {
            cows++;
            last_cow = c;
        }
    }
    return cows >= k;
}

Если в конце такого жадного алгоритма коровы у нас кончились раньше, чем безопасные стойла, то ответ точно не меньше $x$, а если у нас не получилось, то ответ точно меньше $x$.

Теперь мы можем перебрать $x$ и сделать $X = \frac{\max x_i - \min x_i}{k}$ проверок за $O(n)$, но можно и ещё быстрее.

Запустим бинпоиск по $x$ — ведь для каких-то маленьких $x$ коров точно можно расставить, а начиная с каких-то больших — уже нельзя, и как раз это границу нас и просят найти в задаче.

int solve() {
    sort(coords.begin(), coords.end());
    int l = 0; // так как коров меньше, чем стойл, x = 0 нам всегда хватит
    // по условию есть хотя бы 2 коровы,
    // которых мы в лучшем случае отправим в противоположные стойла:
    int r = coords.back() - coords[0] + 1;
    while (r - l > 1) {
        int m = (l + r) / 2;
        if (check(m))
            l = m;
        else
            r = m;
    }
    return l;
}

Каждая проверка у нас работает за $O(n)$, а внешний бинпоиск — за $O(\log n)$ проверок, так что асимптотика будет $O(n \log X)$.

#«Принтеры»

Есть два принтера. Один печатает лист раз в $x$ минут, другой раз в $y$ минут. За сколько минут они напечатают $n$ листов?

$n > 0$

Здесь, в отличие от предыдущей задачи, кажется, существует прямое решение с формулой. Но вместо того, чтобы о нем думать, можно просто свести задачу к обратной. Давайте подумаем, как по числу минут $t$ (ответу) понять, сколько листов напечатается за это время? Очень легко: