Информатика · объяснение и практика
Как искать минимально допустимый ответ по монотонной проверке
Ищем минимальное время изготовления деталей через проверку выполнимости, доказываем монотонность и сохраняем ложную и истинную границы.

В теме Методы алгоритмов: углубление · Учебная карта
Главная мысль
Бинарный поиск по ответу применяют, когда проверка выполнимости монотонна: все значения меньше порога не подходят, а начиная с порога подходят. Тогда ищут границу между ложью и истиной, даже если заранее не выписан отсортированный массив ответов.
Сначала постройте честную проверку
Два станка выпускают по одной детали за 4 и 7 минут. Оба начинают в момент ноль, первая деталь появляется только после полного цикла. Сколько минимум целых минут нужно для пяти деталей? За время t получится floor(t/4)+floor(t/7) деталей. Проверка возвращает истину, если эта сумма не меньше пяти.
Через 11 минут готовы 2+1=3 детали, через 12 — 3+1=4, через 14 — 3+2=5. Более позднее время не уменьшает количество готовых деталей. Поэтому проверка монотонна. Если бы станки портили продукцию после срока хранения, прежнее доказательство перестало бы работать и такую проверку пришлось бы пересмотреть.
Пример
Минимум равен 14 минутам: в момент 13 готовы только 3+1=4 детали.
Нахождение подходящего времени ещё не доказывает минимальность. Соседнее меньшее целое время помогает проверить границу ответа.
Две границы с разным смыслом
Для положительного заказа время 0 заведомо не подходит. Время 20 подходит: один быстрый станок успевает изготовить все пять деталей. Поддерживаем нижнюю границу как ложную, верхнюю как истинную. Проверяем середину: при истине сдвигаем верхнюю границу к ней, при лжи — нижнюю.
Когда границы отличаются на единицу, между ними не осталось непроверенных целых значений. Ответом служит верхняя граница. При такой схеме нельзя одновременно считать нижнюю допустимой: это уже другой инвариант и другие правила обновления. На заказ нулевого количества сразу возвращают ноль, а не используют положительный ложный старт без проверки.
Монотонность важнее знакомого названия метода
Последовательность результатов должна выглядеть как несколько ложных значений, затем только истинные. Проверка «выпущено ровно пять деталей» может снова стать ложной, когда деталей будет шесть, поэтому для нашего поиска она не годится. Условие «не меньше пяти» сохраняет монотонность и соответствует ожиданию заказа.
Количество проверок растёт логарифмически от ширины интервала, но внутри каждой проверки всё ещё нужно посчитать выпуск всех станков. Также проверяют положительность времени цикла и вместимость целого типа при вычислении верхней границы. Никакой бинарный поиск не исправит деление на нулевой цикл или неверную модель одновременного старта. Полезно сравнивать результат с перебором на маленьких заказах.
От чтения к действию
А теперь — вы
Частые вопросы
Можно ли искать по вещественному времени?
Да, но тогда вместо соседних целых границ нужен критерий точности или число итераций. Гарантия точного целого порога не переносится автоматически на приближённый результат.
Что делать, если верхняя граница неизвестна?
Её можно увеличивать, пока проверка не станет истинной, если существование решения доказано и отдельно защищено переполнение. При невозможной задаче такой цикл не должен работать бесконечно.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Почему двоичный поиск требует упорядоченного массива
Как двоичный поиск использует сортировку, сужает полуинтервал кандидатов и отличает позицию вставки от фактического наличия искомого значения.
Открыть темуКак инвариант объясняет правильность накопления суммы
Как инвариант объясняет цикл накопления суммы: начальное состояние, сохранение свойства одним шагом и вывод после конечного числа итераций.
Открыть тему