Koko Eating Bananas

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

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

Q: Почему бинарный поиск работает для скорости поедания?

Для бинарного поиска нужен вопрос с ответом «да» или «нет», ответы на который упорядочены. «Сможет ли Коко закончить со скоростью k?» — такой вопрос: при большей скорости никогда не потребуется больше часов, потому что округлённое вверх значение p / k для каждой кучи может только уменьшаться с ростом k . Поэтому любая скорость ниже ответа не подходит, а любая скорость, начиная с ответа, подходит — и поиск находит границу.

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

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

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

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

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

+10

У Коко есть n куч бананов, где piles[i] — количество бананов в куче 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 часов — на один час больше.

+22 скрытых тестов при отправке

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

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

Подсказки

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

Открыто 0 из 3

Решение

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

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

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

Идея

Начни с одного вопроса: сколько времени потребуется, чтобы съесть груду из p бананов со скоростью k? Коко съедает k бананов в час и не переходит к другой груде в течение того же часа, поэтому на эту груду потребуется p / k часов с округлением вверх. Чтобы съесть груду из 10 бананов со скоростью 4, потребуется 3 часа: 4, 4, затем 2 и перерыв. Сложи время для всех груд и сравни общую сумму с h.

Теперь попробуй скорости по порядку: 1, 2, 3 и так далее, и верни первую, при которой общее время укладывается в h. По построению это наименьшая скорость, поскольку все меньшие скорости уже были проверены и не подошли. Цикл всегда завершается: при скорости, равной размеру самой большой груды, на каждую груду потребуется один час, а h не меньше количества груд.

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

Алгоритм

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

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

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

Идея

Представь, что каждой скорости от 1 до размера самой большой кучи соответствует строка ответов на вопрос «успеем ли закончить с такой скоростью вовремя?». Чем выше скорость, тем меньше часов потребуется на каждую кучу, поэтому общее время может только уменьшаться. Значит, в строке будут ответы «нет, нет, нет», а затем, начиная с некоторого ответа, — «да», без возврата к «нет». Нужно найти первое «да», а упорядоченная строка из ответов «нет» и «да» — именно то, что бинарный поиск делит пополам.

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

Проследим за первым примером: кучи размером 4, 10, 7, 3 и h = 6. Диапазон — от 1 до 10. При скорости 5 потребуется 1 + 2 + 2 + 1 = 6 часов — это подходит, поэтому диапазон становится от 1 до 5. При скорости 3 потребуется 2 + 4 + 3 + 1 = 10 часов — слишком много, поэтому диапазон становится от 4 до 5. При скорости 4 потребуется 1 + 3 + 2 + 1 = 7 часов — всё ещё слишком много, поэтому диапазон становится от 5 до 5, и ответ — 5.

Каждая проверка делит диапазон пополам, поэтому для диапазона скоростей до 10^9 потребуется около 30 проверок. При 5000 кучах на одну проверку это около 150000 шагов вместо триллионов.

Алгоритм

Установите 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-битного числа, который составляет примерно 2.1 × 10^9. При переполнении общее число может оказаться маленьким, и проверку пройдёт скорость, которая слишком мала. Используй 64-битное целое число или прекращай подсчёт, как только общее число превысит h.
Округление не в ту сторону. Целочисленное деление округляет вниз, поэтому 10 / 4 даёт 2, хотя на эту кучу потребуется 3 часа. Округляй вверх с помощью (pile + k-1) / k.
Начало диапазона с 0. Тогда mid может быть равен 0, и при подсчёте часов произойдёт деление на ноль. Наименьшая реальная скорость — 1.
Сдвиг hi к mid - 1, когда mid подходит. Так можно отбросить сам ответ. Когда ищешь первую подходящую скорость, оставляй mid в диапазоне, присваивая hi = mid, и выполняй цикл, пока lo < hi.
Задание hi меньше самой большой кучи. Все скорости меньше неё могут не подойти, когда h равно числу куч, и тогда поиск вернёт неподходящую скорость.

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

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

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

Почему бинарный поиск работает для скорости поедания?

Для бинарного поиска нужен вопрос с ответом «да» или «нет», ответы на который упорядочены. «Сможет ли Коко закончить со скоростью k?» — такой вопрос: при большей скорости никогда не потребуется больше часов, потому что округлённое вверх значение p / k для каждой кучи может только уменьшаться с ростом k. Поэтому любая скорость ниже ответа не подходит, а любая скорость, начиная с ответа, подходит — и поиск находит границу.

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

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

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

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

Python

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

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

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

Ожидается