Koko Eating Bananas

Средняя№875поиск по ответу

Есть кучки бананов и h часов. Каждый час выбираешь одну кучку и съедаешь из неё до k бананов; если в ней меньше, доедаешь её и ждёшь следующего часа. Нужно найти наименьшую целую скорость k, при которой все кучки будут съедены за h часов. Наш пример: кучки [4, 9, 2, 13], h = 6 — ответ 7.

875 Koko Eating BananasРазбор · 1×

Пример: Кучки [4, 9, 2, 13], h = 6. Верхний ряд — скорости 1..13; ниже — сколько часов уходит на каждую кучку на скорости mid.

скорость, бананов в час12345678910111213loкучки49213часы—сумма—
скорость ещё возможнасередина, проверяемотброшенаответ

Самая низкая скорость — 1 банан в час: lo = 1

01/31
сначала · назад · пуск · шаг
Скорость
1function minEatingSpeed(piles, h):
2 lo = 1
3 hi = max(piles) // faster never helps
4 while lo < hi:
5 mid = floor((lo + hi) / 2)
6 hours = 0
7 for each pile in piles:
8 hours = hours + ceil(pile / mid)
9 if hours <= h:
10 hi = mid // in time: keep mid
11 else:
12 lo = mid + 1
13 return lo
состояние
lo
1
hi
–
mid
–
pile
–
hours
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

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

Сложность

Время O(n log m), где n — число кучек, а m — самая большая кучка: пробуем около log m скоростей, и каждая проверка проходит по всем кучкам. Память O(1).

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.