Koko Eating Bananas

Q: Wie hoch ist die zeitliche Komplexität von Koko Eating Bananas?

Die binäre Suche benötigt O(n log m) Zeit, wobei n die Anzahl der Haufen und m der größte Haufen ist. Bei jeder Prüfung wird jeder Haufen einmal gelesen, und der Geschwindigkeitsbereich halbiert sich nach jeder Prüfung. Daher gibt es etwa log2(m) Prüfungen: 30, wenn m = 10^9 ist. Der zusätzliche Speicherbedarf beträgt O(1) .

Q: Warum funktioniert die binäre Suche bei der Essgeschwindigkeit?

Die binäre Suche benötigt eine Ja-oder-Nein-Frage, deren Antworten sortiert sind. „Kann Koko mit der Geschwindigkeit k fertig werden?“ ist eine solche Frage: Bei einer höheren Geschwindigkeit werden nie mehr Stunden benötigt, denn die aufgerundete Zahl p / k für jeden Haufen kann nur kleiner werden, wenn k wächst. Daher scheitert jede Geschwindigkeit unterhalb der Antwort, und jede Geschwindigkeit ab der Antwort ist erfolgreich; die Suche findet also die Grenze.

Q: Was sind die Unter- und Obergrenzen für die Geschwindigkeit?

Die obere Grenze ist der größte Haufen: Bei dieser Geschwindigkeit dauert es genau eine Stunde, jeden Haufen zu essen, und h ist mindestens so groß wie die Anzahl der Haufen, sodass es immer passt. Bei einer höheren Geschwindigkeit braucht man immer noch eine Stunde pro Haufen, daher bringt es nichts, darüber hinaus zu suchen. Die untere Grenze ist 1, und du kannst sie auf die Gesamtzahl der Bananen geteilt durch h , aufgerundet, verschärfen, da Koko höchstens k Bananen pro Stunde isst.

Q: Wie dividiert und rundet man mit Ganzzahlen auf?

Verwende (p + k-1) / k mit ganzzahliger Division. Durch das Addieren von k-1 wird jeder Rest über das nächste Vielfache von k hinausgeschoben, während ein exaktes Vielfaches unverändert bleibt: 10 bei Geschwindigkeit 4 ergibt 13 / 4 = 3 , und 8 bei Geschwindigkeit 4 ergibt 11 / 4 = 2 . So wird Fließkommaarithmetik vermieden, bei der große Werte falsch gerundet werden können.

MittelBinäre Suche

+10

Koko hat n Bananenhaufen, wobei piles[i] die Anzahl der Bananen im Haufen i angibt, und h Stunden, bis die Wächter zurückkommen. Sie wählt eine Essgeschwindigkeit k, eine ganze Anzahl Bananen pro Stunde, und behält sie bei. Jede Stunde isst sie k Bananen aus einem Haufen; wenn darin weniger als k übrig sind, isst sie den Haufen vollständig auf und ruht sich aus, bis die Stunde vorbei ist. Gib die kleinste Geschwindigkeit k zurück, mit der sie alle Haufen innerhalb von h Stunden leeren kann.

Funktion

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

pilesinteger-array: die Anzahl der Bananen in jedem Haufen
hinteger: die Anzahl der Stunden, die Koko hat
Gibt zurückinteger: die kleinste ganzzahlige Essgeschwindigkeit in Bananen pro Stunde, bei der jeder Stapel innerhalb von h Stunden aufgegessen wird

Einschränkungen

1 ≤ piles.length ≤ 5000
1 ≤ piles[i] ≤ 10⁹
piles.length ≤ h ≤ 10⁹, also existiert immer eine Antwort.

Beispiele

Eingabe: piles = [4, 10, 7, 3]h = 6
Ausgabe: 5
Erklärung: Bei Geschwindigkeit 5 benötigen die Stapel 4, 10, 7 und 3 jeweils 1, 2, 2 und 1 Stunden: insgesamt 6, was passt. Bei Geschwindigkeit 4 benötigen sie 1, 3, 2 und 1 Stunden, also 7 Stunden – eine Stunde zu viel.

+22 versteckte Tests beim Einreichen

Weiterführende Frage

Ein verwandtes Problem: Koko hat d Tage und isst ganze Haufen in der vorgegebenen Reihenfolge, wobei sie pro Tag so viele Haufen isst, wie in ein Tageslimit von k Bananen passen. Was ist das kleinste k, und welche zwei Teile deiner binären Suche ändern sich?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Die Antwort hier ist eine Geschwindigkeit, keine Position im Array, und dadurch wird die binäre Suche verborgen. Eine Geschwindigkeit zu prüfen erfordert einen einzigen Durchlauf über die Haufen. Die Prüfungen sind außerdem der Reihe nach angeordnet: Wenn die Geschwindigkeit k rechtzeitig fertig wird, gilt das auch für jede höhere Geschwindigkeit. Du kannst also eine binäre Suche über die Geschwindigkeiten von 1 bis zum größten Haufen durchführen und brauchst etwa 30 Prüfungen, während das Ausprobieren der Geschwindigkeiten nacheinander bis zu einer Milliarde Prüfungen erfordern kann.

Probiere jede Geschwindigkeit ab 1 aufwärts aus

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Beginne mit einer Frage: Wie lange dauert ein Haufen mit p Bananen bei einer Geschwindigkeit von k? Koko isst k pro Stunde und wechselt innerhalb derselben Stunde nie zu einem anderen Haufen, daher dauert der Haufen aufgerundet p / k Stunden. Ein Haufen mit 10 Bananen dauert bei einer Geschwindigkeit von 4 Stunden: 4, 4, dann 2 und eine Pause. Addiere das für alle Haufen und vergleiche die Summe mit h.

Probiere nun die Geschwindigkeiten der Reihe nach aus: 1, 2, 3 und so weiter, und gib die erste zurück, bei der die Gesamtzeit in h passt. Sie ist konstruktionsbedingt die kleinste, da jede langsamere Geschwindigkeit ausprobiert wurde und nicht gereicht hat. Die Schleife hält immer an: Bei der Geschwindigkeit des größten Haufens dauert jeder Haufen eine Stunde, und h ist mindestens so groß wie die Anzahl der Haufen.

Das Problem ist, wie oft die Schleife laufen kann. Bei 5000 Haufen mit jeweils fast 10^9 Bananen und h = 5000 liegt die Antwort nahe bei 10^9, sodass die Schleife etwa eine Milliarde Mal läuft und jeder Prüfschritt alle 5000 Haufen durchgeht: etwa 5 × 10^12 Schritte. Hier ist m der größte Haufen.

Algorithmus

Setze speed = 1.
Zähle die Stunden bei dieser Geschwindigkeit: Addiere für jeden Haufen (pile + speed-1) / speed und verwende eine 64-Bit-Summe.
Wenn die Summe höchstens h beträgt, gib speed zurück.
Andernfalls erhöhe speed um 1 und zähle erneut.

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

Binäre Suche nach der Geschwindigkeit

Idee

Stell dir jede Geschwindigkeit von 1 bis zum größten Haufen als eine Zeile mit Antworten auf die Frage „Schafft diese Geschwindigkeit es rechtzeitig?“ vor. Mit zunehmender Geschwindigkeit braucht jeder Haufen gleich viele oder weniger Stunden, also kann die Gesamtzeit nur sinken. Die Zeile besteht daher aus Nein, Nein, Nein und ab der Antwort aus Ja, ohne dass es wieder zurückgeht. Du suchst das erste Ja, und eine sortierte Zeile aus Nein und Ja ist genau das, was die binäre Suche in zwei Hälften teilt.

Behalte einen Bereich von lo bis hi, der immer die Antwort enthält. Er beginnt bei 1 und dem größten Haufen. Das ist sicher, weil die Geschwindigkeit des größten Haufens eine Stunde pro Haufen benötigt und h dafür ausreicht. Prüfe die mittlere Geschwindigkeit mid. Wenn sie ausreicht, ist die Antwort mid oder langsamer. Setze also hi = mid und behalte mid im Bereich. Wenn sie nicht ausreicht, scheitert jede langsamere Geschwindigkeit ebenfalls. Setze also lo = mid + 1. Wenn lo auf hi trifft, ist diese Geschwindigkeit die Antwort.

Verfolge das erste Beispiel: Haufen 4, 10, 7, 3 mit h = 6. Der Bereich reicht von 1 bis 10. Geschwindigkeit 5 benötigt 1 + 2 + 2 + 1 = 6 Stunden und reicht somit aus. Der Bereich wird also zu 1 bis 5. Geschwindigkeit 3 benötigt 2 + 4 + 3 + 1 = 10 Stunden, zu viele. Der Bereich wird also zu 4 bis 5. Geschwindigkeit 4 benötigt 1 + 3 + 2 + 1 = 7 Stunden, immer noch zu viele. Der Bereich wird also zu 5 bis 5, und die Antwort ist 5.

Jede Prüfung halbiert den Bereich, sodass ein Bereich von bis zu 10^9 Geschwindigkeiten etwa 30 Prüfungen benötigt. Bei 5000 Haufen pro Prüfung sind das etwa 150000 Schritte statt Billionen.

Algorithmus

Setze lo = 1 und hi auf den größten Stapel.
Solange lo < hi gilt, berechne mid = lo + (hi - lo) / 2.
Zähle die Stunden bei Geschwindigkeit mid: Addiere für jeden Stapel (pile + mid-1) / mid zu einer 64-Bit-Summe.
Wenn die Summe höchstens h beträgt, setze hi = mid; andernfalls setze lo = mid + 1.
Wenn die Schleife endet, gib lo zurück.

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

Stolperfallen und Grenzfälle

Die Suche selbst ist kurz. Die Fehler verstecken sich in der Stundenzählung und an den Grenzen des Bereichs.

Überlauf bei der Stundenzählung. Bei Geschwindigkeit 1 benötigen 5000 Bananenhaufen mit 10^9 Bananen 5 × 10^12 Stunden – weit mehr als der 32-Bit-Grenzwert von etwa 2.1 × 10^9. Eine übergelaufene Summe kann einen kleinen Wert ergeben und eine zu langsame Geschwindigkeit die Prüfung bestehen lassen. Zähle mit einer 64-Bit-Ganzzahl oder höre mit dem Zählen auf, sobald die Summe h überschreitet.
Falsch runden. Ganzzahldivision rundet ab, also ergibt 10 / 4 den Wert 2, obwohl dieser Haufen 3 Stunden benötigt. Runde mit (pile + k-1) / k auf.
Den Bereich bei 0 beginnen. Dann kann mid 0 sein und die Stundenzählung würde durch null teilen. Die niedrigste tatsächliche Geschwindigkeit ist 1.
hi auf mid - 1 setzen, wenn mid passt. Dadurch kann die gesuchte Antwort selbst ausgeschlossen werden. Wenn du nach der ersten passenden Geschwindigkeit suchst, behalte mid mit hi = mid bei und wiederhole die Schleife, solange lo < hi gilt.
hi kleiner als den größten Haufen ansetzen. Wenn h der Anzahl der Haufen entspricht, können alle kleineren Geschwindigkeiten scheitern, sodass die Suche eine Geschwindigkeit zurückgibt, die nicht funktioniert.

Häufige Fragen4

Wie hoch ist die zeitliche Komplexität von Koko Eating Bananas?

Die binäre Suche benötigt O(n log m) Zeit, wobei n die Anzahl der Haufen und m der größte Haufen ist. Bei jeder Prüfung wird jeder Haufen einmal gelesen, und der Geschwindigkeitsbereich halbiert sich nach jeder Prüfung. Daher gibt es etwa log2(m) Prüfungen: 30, wenn m = 10^9 ist. Der zusätzliche Speicherbedarf beträgt O(1).

Warum funktioniert die binäre Suche bei der Essgeschwindigkeit?

Die binäre Suche benötigt eine Ja-oder-Nein-Frage, deren Antworten sortiert sind. „Kann Koko mit der Geschwindigkeit k fertig werden?“ ist eine solche Frage: Bei einer höheren Geschwindigkeit werden nie mehr Stunden benötigt, denn die aufgerundete Zahl p / k für jeden Haufen kann nur kleiner werden, wenn k wächst. Daher scheitert jede Geschwindigkeit unterhalb der Antwort, und jede Geschwindigkeit ab der Antwort ist erfolgreich; die Suche findet also die Grenze.

Was sind die Unter- und Obergrenzen für die Geschwindigkeit?

Die obere Grenze ist der größte Haufen: Bei dieser Geschwindigkeit dauert es genau eine Stunde, jeden Haufen zu essen, und h ist mindestens so groß wie die Anzahl der Haufen, sodass es immer passt. Bei einer höheren Geschwindigkeit braucht man immer noch eine Stunde pro Haufen, daher bringt es nichts, darüber hinaus zu suchen. Die untere Grenze ist 1, und du kannst sie auf die Gesamtzahl der Bananen geteilt durch h, aufgerundet, verschärfen, da Koko höchstens k Bananen pro Stunde isst.

Wie dividiert und rundet man mit Ganzzahlen auf?

Verwende (p + k-1) / k mit ganzzahliger Division. Durch das Addieren von k-1 wird jeder Rest über das nächste Vielfache von k hinausgeschoben, während ein exaktes Vielfaches unverändert bleibt: 10 bei Geschwindigkeit 4 ergibt 13 / 4 = 3, und 8 bei Geschwindigkeit 4 ergibt 11 / 4 = 2. So wird Fließkommaarithmetik vermieden, bei der große Werte falsch gerundet werden können.

Python

def minEatingSpeed(piles, h):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

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

Erwartet