Koko Eating Bananas

Q: Jaka jest złożoność czasowa problemu Koko jedzącej banany?

Wyszukiwanie binarne działa w czasie O(n log m) , gdzie n to liczba stosów, a m to największy stos. Każde sprawdzenie odczytuje każdy stos raz, a zakres prędkości zmniejsza się o połowę po każdym sprawdzeniu, więc potrzeba około log2(m) sprawdzeń: 30, gdy m = 10^9 . Dodatkowe miejsce zajmuje O(1) .

Q: Dlaczego wyszukiwanie binarne działa w przypadku szybkości jedzenia?

Wyszukiwanie binarne wymaga pytania, na które można odpowiedzieć „tak” lub „nie”, a odpowiedzi są uporządkowane. „Czy Koko może skończyć przy prędkości k?” to takie pytanie: większa prędkość nigdy nie wymaga więcej godzin, ponieważ zaokrąglony w górę wynik p / k dla każdej sterty może tylko maleć wraz ze wzrostem k . Zatem każda prędkość mniejsza od odpowiedzi nie wystarczy, a każda prędkość od odpowiedzi wzwyż wystarczy — wyszukiwanie znajduje tę granicę.

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

Górna granica to największy stos: przy takiej prędkości zjedzenie każdego stosu zajmuje dokładnie godzinę, a h jest co najmniej równe liczbie stosów, więc zawsze wystarcza czasu. Większa prędkość nadal oznacza godzinę na stos, więc szukanie powyżej tej wartości nic nie daje. Dolna granica wynosi 1. Możesz ją zawęzić do całkowitej liczby bananów podzielonej przez h i 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 z dzieleniem całkowitoliczbowym. Dodanie k-1 przesuwa każdą resztę ponad następną wielokrotność k , a dokładna wielokrotność pozostaje tam, gdzie jest: 10 przy prędkości 4 daje 13 / 4 = 3 , a 8 przy prędkości 4 daje 11 / 4 = 2 . Pozwala to uniknąć liczb zmiennoprzecinkowych, przy których duże wartości mogą zostać zaokrąglone w niewłaściwą stronę.

ŚrednieWyszukiwanie binarne

+10

Koko ma n stosów bananów, gdzie piles[i] oznacza liczbę bananów w stosie i, a strażnicy wrócą za h godzin. Wybiera jedną prędkość jedzenia k, całkowitą liczbę bananów na godzinę, i się jej trzyma. W każdej godzinie zjada k bananów z jednego stosu; jeśli zostanie w nim mniej niż k bananów, kończy go i odpoczywa do końca tej godziny. Zwróć najmniejszą prędkość k, która pozwoli jej zjeść wszystkie stosy w ciągu h godzin.

Funkcja

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

pilesinteger-array: liczba bananów w każdym stosie
hinteger: liczba godzin, które ma Koko
Zwracainteger: najmniejsza całkowita szybkość jedzenia, wyrażona w bananach na godzinę, przy której wszystkie stosy zostaną zjedzone 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 — o jedną godzinę za dużo.

+22 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Podobny problem: Koko ma d dni i zjada całe stosy w podanej kolejności, tyle stosów dziennie, ile zmieści się w dziennym limicie k bananów. Jakie jest najmniejsze k i które dwa elementy wyszukiwania binarnego się zmieniają?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Odpowiedzią jest tutaj prędkość, a nie pozycja w tablicy, co pozwala zastosować wyszukiwanie binarne. Sprawdzenie jednej prędkości wymaga jednego przejścia po stosach. Wyniki sprawdzeń układają się też w kolejności: jeśli prędkość k pozwala skończyć na czas, to każda większa prędkość również. Możesz więc przeprowadzić wyszukiwanie binarne wśród prędkości od 1 do największego stosu i potrzebujesz około 30 sprawdzeń, podczas gdy sprawdzanie prędkości po kolei może wymagać miliarda prób.

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

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

Intuicja

Zacznij od jednego pytania: ile czasu zajmuje zjedzenie stosu p bananów przy prędkości k? Koko zjada k bananów na godzinę i nigdy nie przechodzi na inny stos w trakcie tej samej godziny, więc zjedzenie stosu zajmuje p / k godzin, zaokrąglając w górę. Zjedzenie stosu 10 bananów przy prędkości 4 zajmuje 3 godziny: 4, 4, a potem 2 i odpoczynek. Zsumuj to dla wszystkich stosów i porównaj łączny czas z h.

Teraz sprawdzaj prędkości po kolei: 1, 2, 3 i tak dalej, a następnie zwróć pierwszą, przy której łączny czas mieści się w h. Z definicji jest to najmniejsza prędkość, ponieważ sprawdzono wszystkie mniejsze prędkości i żadna się nie sprawdziła. Pętla zawsze się kończy: przy prędkości równej wielkości największego stosu zjedzenie każdego stosu zajmuje jedną godzinę, a h jest co najmniej równe liczbie stosów.

Problemem jest to, jak długo może działać pętla. Przy 5000 stosach liczących prawie 10^9 bananów i h = 5000 odpowiedź jest bliska 10^9, więc pętla wykonuje się około miliarda razy, a każde sprawdzenie odczytuje wszystkie 5000 stosów: około 5 × 10^12 kroków. W tym przypadku m oznacza wielkość największego stosu.

Algorytm

Ustaw speed = 1.
Policz godziny przy tej prędkości: dla każdego stosu dodaj (pile + speed-1) / speed, używając sumy 64-bitowej.
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

Pomyśl o każdej prędkości od 1 do wielkości największej sterty jak o wierszu odpowiedzi na pytanie „czy przy tej prędkości skończysz na czas?”. Wraz ze wzrostem prędkości każda sterta zajmuje tyle samo godzin lub mniej, więc łączny czas może tylko maleć. Wiersz odpowiedzi zawiera więc „nie, nie, nie”, a następnie — od właściwej odpowiedzi — „tak”, bez powrotu do „nie”. Szukasz pierwszego „tak”, a uporządkowany wiersz z odpowiedziami „nie” i „tak” to dokładnie taki, który wyszukiwanie binarne dzieli na pół.

Utrzymuj zakres od lo do hi, który zawsze obejmuje odpowiedź. Zaczyna się od 1 i wielkości największej sterty. To bezpieczny zakres, ponieważ przy prędkości równej wielkości największej sterty każda sterta wymaga jednej godziny, a h wystarcza na ten czas. Sprawdź środkową prędkość mid. Jeśli się sprawdza, odpowiedzią jest mid lub mniejsza prędkość, więc ustaw hi = mid i pozostaw mid w zakresie. Jeśli się nie sprawdza, każda mniejsza prędkość również nie da rady, więc ustaw lo = mid + 1. Gdy lo zrówna się z hi, ta prędkość jest odpowiedzią.

Prześledź pierwszy przykład: sterty 4, 10, 7, 3 oraz h = 6. Zakres wynosi od 1 do 10. Przy prędkości 5 potrzeba 1 + 2 + 2 + 1 = 6 godzin, więc mieścisz się w limicie, a zakres zmienia się na 1–5. Przy prędkości 3 potrzeba 2 + 4 + 3 + 1 = 10 godzin, czyli za dużo, więc zakres zmienia się na 4–5. Przy prędkości 4 potrzeba 1 + 3 + 2 + 1 = 7 godzin, nadal za dużo, więc zakres zmienia się na 5–5, a odpowiedzią jest 5.

Każde sprawdzenie zmniejsza zakres o połowę, więc dla zakresu obejmującego do 10^9 prędkości potrzeba około 30 sprawdzeń. Przy 5000 stertach na jedno sprawdzenie daje to około 150000 kroków zamiast bilionów.

Algorytm

Ustaw lo = 1, a hi na największy stos.
Gdy lo < hi, oblicz mid = lo + (hi - lo) / 2.
Policz liczbę godzin przy prędkości mid: dodaj (pile + mid-1) / mid dla każdego stosu, sumując w zmiennej 64-bitowej.
Jeśli suma jest nie większa niż h, ustaw hi = mid; w przeciwnym razie ustaw lo = mid + 1.
Gdy pętla się zakończy, 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

Samo wyszukiwanie jest krótkie. Błędy kryją się w liczeniu godzin i na krańcach zakresu.

Przepełnienie przy liczeniu godzin. Przy prędkości 1 zjedzenie 5000 stosów po 10^9 bananów zajmuje 5 × 10^12 godzin, znacznie więcej niż limit 32-bitowy wynoszący około 2.1 × 10^9. Zawinięta suma może okazać się mała i sprawić, że prędkość, która jest za mała, przejdzie sprawdzenie. Używaj 64-bitowej liczby całkowitej albo przestań liczyć, gdy tylko suma przekroczy h.
Zaokrąglanie w niewłaściwą stronę. Dzielenie całkowitoliczbowe zaokrągla w dół, więc 10 / 4 daje 2, a jednak zjedzenie tego stosu zajmuje 3 godziny. Zaokrąglaj w górę za pomocą (pile + k-1) / k.
Rozpoczynanie zakresu od 0. Wtedy mid może wynosić 0, a liczenie godzin będzie dzielić przez zero. Najmniejsza rzeczywista prędkość to 1.
Ustawianie hi na mid - 1, gdy mid spełnia warunek. W ten sposób można odrzucić samą odpowiedź. Szukając pierwszej prędkości, która działa, zachowaj mid, ustawiając hi = mid, i wykonuj pętlę, dopóki lo < hi.
Ustawianie hi poniżej największego stosu. Prędkości mniejsze od tej wartości mogą wszystkie nie spełniać warunku, gdy h jest równe liczbie stosów, więc wyszukiwanie zwróci prędkość, która nie działa.

Najczęstsze pytania4

Jaka jest złożoność czasowa problemu Koko jedzącej banany?

Wyszukiwanie binarne działa w czasie O(n log m), gdzie n to liczba stosów, a m to największy stos. Każde sprawdzenie odczytuje każdy stos raz, a zakres prędkości zmniejsza się o połowę po każdym sprawdzeniu, więc potrzeba około log2(m) sprawdzeń: 30, gdy m = 10^9. Dodatkowe miejsce zajmuje O(1).

Dlaczego wyszukiwanie binarne działa w przypadku szybkości jedzenia?

Wyszukiwanie binarne wymaga pytania, na które można odpowiedzieć „tak” lub „nie”, a odpowiedzi są uporządkowane. „Czy Koko może skończyć przy prędkości k?” to takie pytanie: większa prędkość nigdy nie wymaga więcej godzin, ponieważ zaokrąglony w górę wynik p / k dla każdej sterty może tylko maleć wraz ze wzrostem k. Zatem każda prędkość mniejsza od odpowiedzi nie wystarczy, a każda prędkość od odpowiedzi wzwyż wystarczy — wyszukiwanie znajduje tę granicę.

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

Górna granica to największy stos: przy takiej prędkości zjedzenie każdego stosu zajmuje dokładnie godzinę, a h jest co najmniej równe liczbie stosów, więc zawsze wystarcza czasu. Większa prędkość nadal oznacza godzinę na stos, więc szukanie powyżej tej wartości nic nie daje. Dolna granica wynosi 1. Możesz ją zawęzić do całkowitej liczby bananów podzielonej przez h i 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 z dzieleniem całkowitoliczbowym. Dodanie k-1 przesuwa każdą resztę ponad następną wielokrotność k, a dokładna wielokrotność pozostaje tam, gdzie jest: 10 przy prędkości 4 daje 13 / 4 = 3, a 8 przy prędkości 4 daje 11 / 4 = 2. Pozwala to uniknąć liczb zmiennoprzecinkowych, przy których duże wartości mogą zostać zaokrąglone w niewłaściwą stronę.

Python

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

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

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

Oczekiwane