Koko Eating Bananas

Q: Какова временная сложность задачи «Коко ест бананы»?

Бинарный поиск выполняется за время O(n log m) , где n — количество куч, а m — размер самой большой кучи: примерно log2(m) проверок, 30 при m = 10^9 ; при каждой проверке каждая куча считывается один раз. Дополнительная память составляет O(1) .

Q: Каковы нижняя и верхняя границы скорости?

Верхняя граница — это самая большая куча: при такой скорости на каждую кучу уходит один час, что всегда укладывается в отведённое время. Нижняя граница равна 1, и её можно повысить до общего количества бананов, делённого на h и округлённого вверх, поскольку Коко съедает не более k бананов в час.

Q: Как разделить целые числа с округлением вверх?

Используй (p + k-1) / k с целочисленным делением. Прибавление k-1 переносит любой остаток за следующую кратную k величину, а точное кратное остаётся без изменений: скорость 4 для 10 даёт 13 / 4 = 3 , а для 8 — 11 / 4 = 2 . Числа с плавающей точкой не нужны.

СреднеБинарный поиск

+10

У Коко есть n куч бананов, в куче i находится piles[i] бананов, и у неё есть h часов. Она выбирает скорость поедания k — целое количество бананов в час — и придерживается её. Каждый час она съедает k бананов из одной кучи; если в куче осталось меньше k бананов, она доедает их и отдыхает до конца часа. Верните минимальное значение k, при котором она сможет съесть все бананы из всех куч за h часов.

Функция

minEatingSpeed(piles: integer-array, h: integer) → integer

pilesinteger-array: количество бананов в каждой куче
hinteger: количество часов, которое есть у Коко
Возвращаетinteger: наименьшая целая скорость поедания бананов (бананов в час), при которой все стопки будут съедены за h часов

Ограничения

1 ≤ piles.length ≤ 5000
1 ≤ piles[i] ≤ 10⁹
piles.length ≤ h ≤ 10⁹, поэтому ответ всегда существует.

Примеры

Ввод: piles = [4, 10, 7, 3]h = 6
Вывод: 5
Пояснение: При скорости 5 на стопки 4, 10, 7 и 3 уйдёт 1, 2, 2 и 1 час: всего 6, что укладывается в лимит. При скорости 4 на них уйдёт 1, 3, 2 и 1 час, то есть 7.

Дополнительный вопрос

Задача о Коко: Коко съедает целые груды бананов по порядку, не более k бананов в день, за d дней. Каково наименьшее значение k и что меняется в вашем поиске?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Ответ — это скорость, а не позиция в массиве, и это подсказывает, что здесь нужен бинарный поиск. Проверка одной скорости требует одного прохода по кучам, и если при скорости k всё заканчивается вовремя, то при любой большей скорости — тоже. Поэтому применим бинарный поиск к скоростям от 1 до самой большой кучи: около 30 проверок вместо миллиарда.

Попробуйте каждую скорость, начиная с 1

Верно, но не успевает на самых больших тестах

Идея

Коко никогда не переходит к другой куче в течение часа, поэтому на кучу из p бананов при скорости k требуется p / k часов с округлением вверх: 10 бананов при скорости 4 — это 3 часа. Пробуй скорости 1, 2, 3 и так далее и возвращай первую, при которой общее время укладывается в h. Это минимальная скорость, потому что все более низкие скорости не подошли, а цикл останавливается на скорости, равной размеру самой большой кучи: при ней на каждую кучу требуется один час.

Если m — размер самой большой кучи, то потребуется до m проверок для n куч: около 5 × 10^12 шагов для 5000 куч размером около 10^9 при h = 5000.

Алгоритм

Установи speed = 1.
Посчитай количество часов при такой скорости: для каждой кучи прибавь (pile + speed-1) / speed, используя 64-битную сумму.
Если сумма не больше h, верни speed.
Иначе увеличь speed на 1 и посчитай снова.

def minEatingSpeed(piles, h):
    speed = 1
    while True:
        hours = 0
        for pile in piles:
            hours += (pile + speed - 1) // speed  # a started pile costs a whole hour
        if hours <= h:
            return speed
        speed += 1

Двоичный поиск по скорости

Идея

По мере увеличения скорости для каждой кучи требуется столько же или меньше часов, поэтому ответы на вопрос «успеет ли такая скорость за отведённое время?» идут в порядке «нет, нет, нет, затем да» — начиная с некоторой скорости ответы будут «да». Бинарный поиск находит первую такую скорость.

Поддерживай диапазон от lo до hi, который всегда содержит ответ. Изначально это диапазон от 1 до размера самой большой кучи: при такой скорости на каждую кучу уходит один час, и она укладывается в отведённое время. Если средняя скорость mid укладывается в отведённое время, ответ равен mid или меньше, поэтому присвой hi = mid. Если нет, любая меньшая скорость тоже не подойдёт, поэтому присвой lo = mid + 1. Когда lo сравняется с hi, это и будет ответ.

В первом примере диапазон начинается с 1–10. Скорость 5 подходит, поэтому диапазон становится 1–5; при скорости 3 требуется 10 часов, поэтому диапазон становится 4–5; при скорости 4 требуется 7 часов, поэтому диапазон становится 5–5.

Алгоритм

Установите lo = 1, а hi — равным размеру самой большой кучи.
Пока lo < hi, вычисляйте mid = lo + (hi - lo) / 2.
Подсчитайте количество часов при скорости mid: для каждой кучи прибавляйте (pile + mid-1) / mid к 64-битной сумме.
Если сумма не больше h, установите hi = mid; иначе установите lo = mid + 1.
Верните lo.

def minEatingSpeed(piles, h):
    lo, hi = 1, max(piles)  # the largest pile always works: one hour per pile
    while lo < hi:
        mid = lo + (hi - lo) // 2
        hours = 0
        for pile in piles:
            hours += (pile + mid - 1) // mid
        if hours <= h:
            hi = mid  # mid works, so the answer is mid or slower
        else:
            lo = mid + 1  # mid is too slow, so the answer is faster
    return lo

Ловушки и крайние случаи

Переполнение при подсчёте часов. При скорости 1 5000 куч по 10^9 бананов требуют 5 × 10^12 часов — это превышает предел 32-битного числа, и переполнение суммы может привести к тому, что подходящей окажется слишком низкая скорость. Используй 64-битный тип для подсчёта или прекращай подсчёт, как только сумма превысит h.
Округление вниз. 10 / 4 даёт 2, хотя эта куча требует 3 часов.
Начало диапазона с 0. Тогда mid может оказаться равным 0, и при подсчёте произойдёт деление на ноль.
Установка hi = mid - 1, когда mid подходит. Так можно отбросить правильный ответ.
Начало поиска с hi, меньшего, чем самая большая куча. Когда h равно количеству куч, любая меньшая скорость не подходит, и поиск вернёт одну из них.

Частые вопросы3

Какова временная сложность задачи «Коко ест бананы»?

Бинарный поиск выполняется за время O(n log m), где n — количество куч, а m — размер самой большой кучи: примерно log2(m) проверок, 30 при m = 10^9; при каждой проверке каждая куча считывается один раз. Дополнительная память составляет O(1).

Каковы нижняя и верхняя границы скорости?

Верхняя граница — это самая большая куча: при такой скорости на каждую кучу уходит один час, что всегда укладывается в отведённое время. Нижняя граница равна 1, и её можно повысить до общего количества бананов, делённого на h и округлённого вверх, поскольку Коко съедает не более k бананов в час.

Как разделить целые числа с округлением вверх?

Используй (p + k-1) / k с целочисленным делением. Прибавление k-1 переносит любой остаток за следующую кратную k величину, а точное кратное остаётся без изменений: скорость 4 для 10 даёт 13 / 4 = 3, а для 8 — 11 / 4 = 2. Числа с плавающей точкой не нужны.

def minEatingSpeed(piles, h):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргументы

piles = [4, 10, 7, 3]
h = 6

Ожидаемый вывод