Koko Eating Bananas

Q: Jaka jest złożoność czasowa problemu „Koko Eating Bananas”?

Wyszukiwanie binarne działa w czasie O(n log m) , gdzie n to liczba stosów, a m to największy stos: około log2(m) sprawdzeń, 30, gdy m = 10^9 , z których każde odczytuje każdy stos jeden raz. Dodatkowe zużycie pamięci wynosi O(1) .

Q: Jakie są dolna i górna granica prędkości?

Górna granica to największy stos: przy takiej szybkości zjedzenie każdego stosu zajmuje godzinę, co zawsze mieści się w limicie. Dolna granica wynosi 1 i można ją zwiększyć do łącznej liczby bananów podzielonej przez h , zaokrąglonej w górę, ponieważ Koko zjada najwyżej k bananów na godzinę.

Q: Jak dzielić liczby całkowite i zaokrąglać wynik w górę?

Użyj (p + k-1) / k przy dzieleniu całkowitym. Dodanie k-1 przesuwa każdą resztę poza kolejną wielokrotność k , a dokładna wielokrotność pozostaje bez zmian: 10 przy prędkości 4 daje 13 / 4 = 3 , a 8 daje 11 / 4 = 2 . Nie są potrzebne liczby zmiennoprzecinkowe.

ŚrednieWyszukiwanie binarne

+10

Koko ma n stosów bananów, przy czym w stosie i znajduje się piles[i] bananów, oraz h godzin. Wybiera prędkość jedzenia k, czyli całkowitą liczbę bananów na godzinę, i je w tym tempie. W każdej godzinie zjada k bananów z jednego stosu; jeśli zostanie w nim mniej niż k bananów, zjada je do końca i odpoczywa do końca tej godziny. Zwróć najmniejsze k, które pozwoli jej zjeść wszystkie banany ze wszystkich stosów w ciągu h godzin.

Funkcja

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

pilesinteger-array: liczba bananów w każdej stercie
hinteger: liczba godzin, które ma Koko
Zwracainteger: najmniejsza całkowita prędkość jedzenia, wyrażona w bananach na godzinę, która pozwala zjeść wszystkie stosy w ciągu h godzin

Ograniczenia

1 ≤ piles.length ≤ 5000
1 ≤ piles[i] ≤ 10⁹
piles.length ≤ h ≤ 10⁹, więc odpowiedź zawsze istnieje.

Przykłady

Wejście: piles = [4, 10, 7, 3]h = 6
Wyjście: 5
Wyjaśnienie: Przy prędkości 5 stosy 4, 10, 7 i 3 zajmują odpowiednio 1, 2, 2 i 1 godzinę: łącznie 6, co się mieści. Przy prędkości 4 zajmują 1, 3, 2 i 1 godzinę, czyli 7.

Pytanie dodatkowe

Twin problem: Koko zjada całe stosy po kolei, najwyżej k bananów dziennie, w ciągu d dni. Jakie jest najmniejsze k i co zmienia się w twoim wyszukiwaniu?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Odpowiedzią jest prędkość, a nie pozycja w tablicy — dzięki temu można zastosować wyszukiwanie binarne. Sprawdzenie jednej prędkości wymaga jednego przejścia po stosach, a jeśli przy prędkości k uda się skończyć na czas, uda się to również przy każdej większej prędkości. Zastosuj więc wyszukiwanie binarne wśród prędkości od 1 do wielkości największego stosu: około 30 sprawdzeń zamiast nawet miliarda.

Wypróbuj każdą prędkość, zaczynając od 1

Poprawne, ale nie kończy się na największych testach

Intuicja

Koko nigdy nie przenosi się na inną stertę w ciągu godziny, więc zjedzenie sterty p bananów zajmuje p / k godzin, zaokrąglając w górę: przy prędkości 4 zjedzenie 10 bananów zajmuje 3 godziny. Wypróbuj prędkości 1, 2, 3 i tak dalej, a następnie zwróć pierwszą, przy której łączny czas mieści się w h. Jest to najmniejsza prędkość, ponieważ każda mniejsza się nie sprawdziła, a pętla kończy się na prędkości równej wielkości największej sterty — wtedy zjedzenie każdej sterty zajmuje godzinę.

Jeśli m oznacza największą stertę, wykonujemy do m sprawdzeń n stert: około 5 × 10^12 kroków dla 5000 stert liczących blisko 10^9 bananów i h = 5000.

Algorytm

Ustaw speed = 1.
Policz godziny przy tej prędkości: dla każdej sterty dodaj (pile + speed-1) / speed, używając 64-bitowej sumy.
Jeśli suma wynosi co najwyżej h, zwróć speed.
W przeciwnym razie zwiększ speed o 1 i policz ponownie.

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

Wyszukiwanie binarne prędkości

Intuicja

Gdy szybkość rośnie, zjedzenie każdej sterty zajmuje tyle samo godzin lub mniej, więc odpowiedzi na pytanie „czy ta szybkość pozwala zdążyć na czas?” układają się od tego miejsca jako: nie, nie, nie, a potem tak. Wyszukiwanie binarne znajduje pierwszą odpowiedź „tak”.

Utrzymuj zakres od lo do hi, który zawsze zawiera odpowiedź. Na początku wynosi on od 1 do największej sterty, ponieważ przy tej szybkości zjedzenie każdej sterty zajmuje jedną godzinę, więc mieści się w limicie. Jeśli środkowa szybkość mid mieści się w limicie, odpowiedzią jest mid lub mniejsza szybkość, więc ustaw hi = mid. Jeśli nie, każda mniejsza szybkość również się nie sprawdzi, więc ustaw lo = mid + 1. Gdy lo zrówna się z hi, otrzymasz odpowiedź.

W pierwszym przykładzie zakres zaczyna się od 1 do 10. Szybkość 5 mieści się w limicie, więc zakres zmienia się na 1 do 5; przy szybkości 3 potrzeba 10 godzin, więc zakres zmienia się na 4 do 5; przy szybkości 4 potrzeba 7 godzin, więc zakres zmienia się na 5 do 5.

Algorytm

Ustaw lo = 1, a hi na największą stertę.
Gdy lo < hi, oblicz mid = lo + (hi - lo) / 2.
Policz liczbę godzin przy prędkości mid: dodaj (pile + mid-1) / mid dla każdej sterty, zapisując sumę w 64-bitowej zmiennej.
Jeśli suma jest nie większa niż h, ustaw hi = mid; w przeciwnym razie ustaw lo = mid + 1.
Zwróć 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

Pułapki i przypadki brzegowe

Przepełnienie przy zliczaniu godzin. Przy prędkości 1 zjedzenie 5000 stosów po 10^9 bananów zajmuje 5 × 10^12 godzin, czyli przekracza limit 32-bitowy, a zawinięta suma może sprawić, że przejdzie wolna prędkość. Zliczaj w 64 bitach albo przerwij, gdy suma przekroczy h.
Zaokrąglanie w dół. 10 / 4 daje 2, a jednak zjedzenie tego stosu zajmuje 3 godziny.
Rozpoczęcie zakresu od 0. Wtedy mid może wynosić 0, a przy zliczaniu nastąpi dzielenie przez zero.
Ustawienie hi = mid - 1, gdy mid pasuje. Może to wykluczyć odpowiedź.
Rozpoczęcie od wartości hi mniejszej niż największy stos. Gdy h jest równe liczbie stosów, każda mniejsza prędkość nie spełnia warunku, a wyszukiwanie zwraca jedną z nich.

Najczęstsze pytania3

Jaka jest złożoność czasowa problemu „Koko Eating Bananas”?

Wyszukiwanie binarne działa w czasie O(n log m), gdzie n to liczba stosów, a m to największy stos: około log2(m) sprawdzeń, 30, gdy m = 10^9, z których każde odczytuje każdy stos jeden raz. Dodatkowe zużycie pamięci wynosi O(1).

Jakie są dolna i górna granica prędkości?

Górna granica to największy stos: przy takiej szybkości zjedzenie każdego stosu zajmuje godzinę, co zawsze mieści się w limicie. Dolna granica wynosi 1 i można ją zwiększyć do łącznej liczby bananów podzielonej przez h, zaokrąglonej w górę, ponieważ Koko zjada najwyżej k bananów na godzinę.

Jak dzielić liczby całkowite i zaokrąglać wynik w górę?

Użyj (p + k-1) / k przy dzieleniu całkowitym. Dodanie k-1 przesuwa każdą resztę poza kolejną wielokrotność k, a dokładna wielokrotność pozostaje bez zmian: 10 przy prędkości 4 daje 13 / 4 = 3, a 8 daje 11 / 4 = 2. Nie są potrzebne liczby zmiennoprzecinkowe.

def minEatingSpeed(piles, h):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

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

Oczekiwany wynik