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

Материал из Algocode wiki
Версия от 16:28, 10 октября 2019; KiKoS (обсуждение | вклад) (→‎Бинарный поиск по ответу)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

В этой статье на примере нескольких задач будет рассмотрена важная разновидность бинарного поиска.

Пример: "Коровы в стойла"

Условие: На прямой расположены $N$ стойл (даны их координаты на прямой), в которые необходимо расставить $K$ коров так, чтобы минимальное расcтояние между коровами было как можно больше. Гарантируется, что $1 < K < N$.

Решение:

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

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

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

То есть если мы знаем расстояние $X$, то мы можем за $O(n)$ проверить, можно ли расставить $K$ коров на таком расстоянии. Запустим бинпоиск по $X$, ведь при слишком маленьком $X$ коров точно можно расставить, а при слишком большом - нельзя, и как раз эту границу и просят найти в задаче ("как можно больше").

Осталось точно определить границы, то есть изначальные значения $left$ и $right$. Нам точно хватит расстояния $0$, так как гарантируется, что коров меньше, чем стойл. И точно не хватит расстояния max_coord - min_coord + 1, так как по условию есть хотя бы $2$ коровы.

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

int solve() {
    sort(coords.begin(), coords.end());
    int left = 0;
    int right = coords.back() - coords[0] + 1;
    while (right - left > 1) {
        int mid = (left + right) / 2;
        if (check(mid)) {
            left = mid;
        } else {
            right = mid;
        }
    }
    return left;
}


Общий принцип

Такой метод и называется бинпоиск по ответу.

По сути вся идея заключается в том, чтобы сформулировать задачу "найдите максимальное $X$, такое что какое-то свойство от $X$ выполняется" и решить её бинпоиском.

Пример: "Очень Легкая Задача

Условие: есть два принтера, один печатает лист раз в $x$ минут, другой раз в $y$ минут. За сколько минут они напечатают $N$ листов? $N > 0$

Решение: Здесь, в отличие от предыдущей задачи, кажется, существует прямое решение с формулой. Но вместо того, чтобы о нем думать, можно просто свести задачу к обратной. Давайте подумаем, как по числу минут $T$ (ответу) понять, сколько листов напечатается за это время? Очень легко: $$\biggl\lfloor\frac{T}{x}\biggr\rfloor + \biggl\lfloor\frac{T}{y}\biggr\rfloor$$

Ясно, что за $0$ минут $N$ листов распечатать нельзя, а за $xN$ минут один только первый принтер успеет напечатать $N$ листов. Поэтому $0$ и $xN$ - это подходящие первые границы для бинарного поиска.



Автор конспекта: Полина Романченко

По всем вопросам пишите в telegram @Romanchenko