Бинарный поиск по ответу на Python: как решать + 7 задач с проверкой

Бинарный поиск по ответу — это приём, когда мы не перебираем варианты решения напрямую, а ищем искомое число (время, скорость, уровень, максимальную нагрузку) через проверку: «если ответ равен X, реально ли выполнить условие?». В задачах он встречается там, где нужно найти минимум/максимум при больших ограничениях: сколько минут нужно, какая минимальная скорость, какой минимальный уровень сжатия, как минимизировать «худший рейс» и т.п.

Как распознать

Задача почти наверняка про этот приём, если:

• просят минимальное/максимальное целое значение;
• можно написать быструю проверку ok(X) (уложимся ли за X минут, хватит ли скорости X, можно ли сделать не хуже X);
• при увеличении X ответ проверки меняется один раз: сначала «нет», потом всегда «да» (или наоборот) — это называется монотонность.

Суть приёма

Мы выбираем границы, где точно «не подходит» и где точно «подходит», и бинарным поиском сужаем диапазон. Проверка ok(X) обычно считается за O(n) или O(n log n), а сам поиск делает около 60 шагов для 64-битного диапазона — поэтому вместо перебора до 10^9 или 10^18 получается быстро.

С чего начать учиться

• Научиться формулировать ok(X) и доказать монотонность одной фразой.
• Подбирать границы: нижняя (0/1/минимальный возможный) и верхняя (достаточно большая, чтобы точно сработало).
• Аккуратно работать с 64-битными числами (время, суммы, произведения).
• Проверять крайние случаи: k = 1, очень большие a[i], один станок.

Ниже — задачи с автопроверкой и разбором подхода, чтобы набить руку на разных формулировках.