Выбор ответа Middle Бинарный поиск обновлено
Бинпоиск по ответу
Вопрос
Есть n кучек бананов и h часов, за час можно съесть не больше k бананов из одной кучки. Найти минимальную k. Как подойти?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Бинпоиск по k: проверка «успеем ли за h часов» монотонна по k. Если со скоростью k успеваем, то и с любой большей успеем: предикат монотонен, значит можно искать минимальную подходящую k бинпоиском.
Варианты ответа
- Жадно взять k равным максимальной кучке, это и есть ответ
- Отсортировать кучки и взять k равным медиане их размеров
- Бинпоиск по k: проверка «успеем ли за h часов» монотонна по kправильный ответ
- Перебор k от 1, пока не успеем: это оптимально по времени
Разбор
Если со скоростью k успеваем, то и с любой большей успеем: предикат монотонен, значит можно искать минимальную подходящую k бинпоиском. Проверка O(n), итого O(n log max).
- Максимальная кучка даёт допустимую, но не минимальную скорость.
- Медиана не связана с ответом.
- Линейный перебор k O(n · max), может быть очень долго.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.