Почему это работает
- Чем быстрее ешь, тем меньше нужно часов. Поэтому по скоростям 1, 2, 3, … проверки «успеваем?» идут «нет, …, нет, да, …, да», а ответ — первое «да».
- На кучку уходит ceil(pile / speed) часов: за час не больше speed бананов и никогда две кучки за один час. Поэтому маленькая кучка всё равно стоит целого часа, как кучка из 2 на скорости 6.
- Если на mid успеваем, он может быть ответом, и hi = mid его оставляет. Если нет, на всех скоростях ниже тоже не успеть: lo = mid + 1.
Сложность
Время O(n log m), где n — число кучек, а m — самая большая кучка: пробуем около log m скоростей, и каждая проверка проходит по всем кучкам. Память O(1).
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗