Koko Eating Bananas
Koko ha n mucchi di banane, dove piles[i] è il numero di banane nel mucchio i, e h ore prima che tornino le guardie. Sceglie una velocità di consumo k, un numero intero di banane all’ora, e la mantiene. Ogni ora mangia k banane da un mucchio; se in quel mucchio ne restano meno di k, lo finisce e riposa fino alla fine dell’ora. Restituisci la velocità minima k che le consente di finire tutti i mucchi entro h ore.
Funzione
- pilesinteger-array
- il numero di banane in ogni mucchio
- hinteger
- il numero di ore che Koko ha
- Restituisceinteger
- la velocità intera minima con cui mangiare, in banane all’ora, che permette di finire ogni mucchio entro h ore
Vincoli
1 ≤ piles.length ≤ 50001 ≤ piles[i] ≤ 109piles.length ≤ h ≤ 109, quindi esiste sempre una risposta.
Esempi
- Input
- piles = [4, 10, 7, 3]h = 6
- Output
- 5
- Spiegazione
- Alla velocità 5, le pile 4, 10, 7 e 3 richiedono 1, 2, 2 e 1 ore: 6 in totale, il che va bene. Alla velocità 4 richiedono 1, 3, 2 e 1 ore, per un totale di 7, un'ora di troppo.
- Input
- piles = [30, 11, 23, 4, 20]h = 5
- Output
- 30
- Spiegazione
- Cinque mucchi e cinque ore lasciano esattamente un’ora per mucchio, quindi la velocità deve consentire di finire il mucchio più grande, 30, in un’ora. A una velocità di 29 quel mucchio richiederebbe una seconda ora.
- Input
- piles = [5, 9, 2]h = 20
- Output
- 1
- Spiegazione
- Alla velocità 1, i mucchi richiedono 5 + 9 + 2 = 16 ore, ben al di sotto delle 20. Non esiste una velocità inferiore a 1, quindi la risposta è 1.
+22 test nascosti all’invio
Per approfondire
Un problema gemello: Koko ha d giorni e mangia interi mucchi nell’ordine indicato, tutti i mucchi che riesce a mangiare in un giorno entro il limite giornaliero di k banane. Qual è il valore minimo di k e quali due parti della tua ricerca binaria cambiano?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Fissa una velocità
k. Quante ore ci vogliono per mangiare una pila dipbanane a quella velocità, dato che Koko non cambia pila durante un’ora? Quante ore ci vogliono per mangiare tutte le pile?Se la velocità
ktermina in tempo, lo fa anche ogni velocità maggiore. Le velocità che funzionano formano una sequenza continua che inizia dalla risposta.Esegui una ricerca binaria sulle velocità da 1 al mucchio più grande. Conta le ore alla velocità intermedia in un solo passaggio: se rientrano in
h, la risposta è al massimo la velocità intermedia; altrimenti è superiore.
Soluzione
La risposta qui è una velocità, non una posizione nell’array, e questo nasconde la ricerca binaria. Verificare una velocità richiede un solo passaggio sui mucchi. Anche le verifiche sono ordinate: se la velocità k termina in tempo, lo fanno anche tutte le velocità maggiori. Quindi puoi eseguire una ricerca binaria sulle velocità da 1 fino al mucchio più grande e ti serviranno circa 30 verifiche, mentre provandole una per una potrebbero servirne un miliardo.
Prova tutte le velocità a partire da 1
Corretto, ma non termina sui test più grandi
Intuizione
Inizia con una domanda: quanto tempo ci vuole perché Koko mangi un mucchio di p banane alla velocità k? Koko mangia k banane all’ora e non passa a un altro mucchio durante la stessa ora, quindi per mangiare il mucchio servono p / k ore, arrotondate per eccesso. Per mangiare un mucchio di 10 banane alla velocità 4 ci vogliono 3 ore: 4, 4, poi 2 e una pausa. Somma il tempo per tutti i mucchi e confronta il totale con h.
Ora prova le velocità in ordine, 1, 2, 3 e così via, e restituisci la prima per cui il tempo totale rientra in h. Per costruzione è la più bassa, perché tutte le velocità inferiori sono state provate e non hanno funzionato. Il ciclo si interrompe sempre: alla velocità pari a quella del mucchio più grande, ogni mucchio richiede un’ora, e h è almeno pari al numero di mucchi.
Il problema è quanto a lungo può andare avanti il ciclo. Con 5000 mucchi da quasi 10^9 banane e h = 5000, la risposta è vicina a 10^9, quindi il ciclo viene eseguito circa un miliardo di volte e ogni controllo legge tutti i 5000 mucchi: circa 5 × 10^12 passaggi. Qui m è il mucchio più grande.
Algoritmo
- Imposta
speed = 1. - Conta le ore a questa velocità: per ogni mucchio aggiungi
(pile + speed-1) / speed, usando un totale a 64 bit. - Se il totale è al massimo
h, restituiscispeed. - Altrimenti aggiungi 1 a
speede conta di nuovo.
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 += 1Ricerca binaria sulla velocità
Intuizione
Considera ogni velocità da 1 fino alla pila più grande come una riga di risposte alla domanda «questa velocità permette di finire in tempo?». Man mano che la velocità aumenta, ogni pila richiede lo stesso numero di ore o meno, quindi il totale può solo diminuire. La riga quindi mostra no, no, no e poi sì, a partire dalla risposta sì, senza più tornare indietro. Cerchi il primo sì, e una riga ordinata di no e sì è proprio ciò che la ricerca binaria divide a metà.
Mantieni un intervallo da lo a hi che contenga sempre la risposta. Inizia da 1 e dalla pila più grande: è una scelta sicura perché la velocità pari alla pila più grande richiede un'ora per pila e h è sufficiente. Controlla la velocità centrale mid. Se è sufficiente, la risposta è mid o una velocità inferiore, quindi imposta hi = mid e mantieni mid nell'intervallo. Se non è sufficiente, anche tutte le velocità inferiori non lo saranno, quindi imposta lo = mid + 1. Quando lo raggiunge hi, quella velocità è la risposta.
Segui il primo esempio: pile 4, 10, 7, 3 con h = 6. L'intervallo va da 1 a 10. La velocità 5 richiede 1 + 2 + 2 + 1 = 6 ore, quindi è sufficiente e l'intervallo diventa da 1 a 5. La velocità 3 richiede 2 + 4 + 3 + 1 = 10 ore, troppe, quindi l'intervallo diventa da 4 a 5. La velocità 4 richiede 1 + 3 + 2 + 1 = 7 ore, ancora troppe, quindi l'intervallo diventa da 5 a 5 e la risposta è 5.
Ogni controllo dimezza l'intervallo, quindi un intervallo di velocità fino a 10^9 richiede circa 30 controlli. Con 5000 pile per controllo, sono circa 150000 passaggi invece di migliaia di miliardi.
Algoritmo
- Imposta
lo = 1ehial mucchio più grande. - Mentre
lo < hi, calcolamid = lo + (hi - lo) / 2. - Conta le ore alla velocità
mid: aggiungi(pile + mid-1) / midper ogni mucchio, usando un totale a 64 bit. - Se il totale è al massimo
h, impostahi = mid; altrimenti impostalo = mid + 1. - Quando il ciclo termina, restituisci
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
Trappole e casi limite
La ricerca in sé è breve. I bug si nascondono nel conteggio delle ore e nei limiti dell'intervallo.
- Overflow del conteggio delle ore. A velocità 1, 5000 pile da
10^9banane richiedono5 × 10^12ore, ben oltre il limite a 32 bit di circa2.1 × 10^9. Un totale che va in overflow può risultare piccolo e far superare il controllo a una velocità troppo bassa. Conta usando un intero a 64 bit oppure interrompi il conteggio non appena il totale superah. - Arrotondare nella direzione sbagliata. La divisione intera arrotonda per difetto, quindi
10 / 4dà 2, ma quella pila richiede 3 ore. Arrotonda per eccesso con(pile + k-1) / k. - Iniziare l'intervallo da 0. In tal caso,
midpuò essere 0 e il conteggio delle ore divide per zero. La velocità reale più bassa è 1. - Spostare
hiamid - 1quandomidè sufficiente. Così potresti scartare la risposta stessa. Quando cerchi la prima velocità che funziona, mantienimidconhi = mide usa un ciclo mentrelo < hi. - Iniziare con
hiinferiore alla pila più grande. Le velocità inferiori potrebbero fallire tutte quandohè uguale al numero di pile, quindi la ricerca restituirebbe una velocità che non funziona.
Domande frequenti4
Qual è la complessità temporale di Koko Eating Bananas?
La ricerca binaria richiede un tempo O(n log m), dove n è il numero di pile e m la pila più grande. Ogni controllo legge ogni pila una volta e l’intervallo delle velocità si dimezza dopo ogni controllo, quindi ci sono circa log2(m) controlli: 30 quando m = 10^9. Lo spazio aggiuntivo è O(1).
Perché la ricerca binaria funziona sulla velocità con cui si mangia?
La ricerca binaria richiede una domanda con risposta sì o no i cui esiti siano ordinati. «Koko riesce a finire alla velocità k?» è una di queste: una velocità maggiore non richiede mai più ore, perché il valore di ogni pila, p / k arrotondato per eccesso, può solo diminuire all’aumentare di k. Quindi tutte le velocità inferiori alla risposta non sono sufficienti, mentre tutte le velocità pari o superiori alla risposta lo sono, e la ricerca trova il confine.
Quali sono i limiti minimo e massimo della velocità?
Il limite superiore è il mucchio più grande: a quella velocità ogni mucchio richiede esattamente un'ora e h è almeno pari al numero di mucchi, quindi è sempre sufficiente. Una velocità maggiore richiede comunque un'ora per mucchio, quindi non serve a nulla cercare oltre. Il limite inferiore è 1 e puoi restringerlo al numero totale di banane diviso per h, arrotondato per eccesso, perché Koko mangia al massimo k banane all'ora.
Come si divide e si arrotonda per eccesso con gli interi?
Usa (p + k-1) / k con la divisione intera. Aggiungere k-1 spinge qualsiasi resto oltre il multiplo successivo di k, mentre un multiplo esatto rimane dov’è: 10 alla velocità 4 dà 13 / 4 = 3, e 8 alla velocità 4 dà 11 / 4 = 2. Evita i numeri in virgola mobile, con cui i valori grandi possono essere arrotondati in modo errato.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
Python
def minEatingSpeed(piles, h):
# Scrivi il codice quiCaso 1
Caso 2
Caso 3
Input
piles = [4, 10, 7, 3] h = 6
Atteso
5