Бинарный поиск по ответу - Алгоритмика (original) (raw)

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

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

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

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

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

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

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

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;
}

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

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

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

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(n)O(n), а внешний бинпоиск — за O(logn)O(\log n)O(logn) проверок, так что асимптотика будет O(nlogX)O(n \log X)O(nlogX).

#«Принтеры»

Есть два принтера. Один печатает лист раз в xxx минут, другой раз в yyy минут. За сколько минут они напечатают nnn листов?

n>0n > 0n>0

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

leftlfloorfractxrightrfloor+leftlfloorfractyrightrfloor\left \lfloor \frac{t}{x} \right \rfloor + \left \lfloor \frac{t}{y} \right \rfloorleftlfloorfractxrightrfloor+leftlfloorfractyrightrfloor Ясно, что за 000 минут nnn листов распечатать нельзя, а за xcdotnx \cdot nxcdotn минут один только первый принтер успеет напечатать nnn листов. Поэтому 000 и xnxnxn — это подходящие изначальные границы для бинарного поиска.