Бинарный поиск по ответу
Содержание
Бинарный поиск по ответу
В этой статье на примере нескольких задач будет рассмотрена важная разновидность бинарного поиска.
Пример: "Коровы в стойла"
Условие: На прямой расположены $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