Koko Eating Bananas

Q: Qual è la complessità temporale di Koko Eating Bananas?

La ricerca binaria ha una complessità temporale di O(n log m) , dove n è il numero di pile e m la pila più grande: circa log2(m) controlli, 30 quando m = 10^9 , ognuno dei quali legge ogni pila una volta. Lo spazio aggiuntivo è O(1) .

Q: Quali sono il limite inferiore e il limite superiore della velocità?

Il limite superiore è il mucchio più grande: lì ogni mucchio richiede un'ora, il che è sempre sufficiente. Il limite inferiore è 1 e puoi aumentarlo fino al numero totale di banane diviso per h , arrotondato per eccesso, perché Koko mangia al massimo k banane all'ora.

Q: 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 resta invariato: 10 alla velocità 4 dà 13 / 4 = 3 , e 8 dà 11 / 4 = 2 . Non serve la virgola mobile.

MedioRicerca binaria

+10

Koko ha n mucchi di banane, con piles[i] banane nel mucchio i, e h ore. 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 si riposa fino alla fine dell’ora. Restituisci il valore minimo di k che le permette di finire tutti i mucchi entro h ore.

Funzione

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

pilesinteger-array: il numero di banane in ogni mucchio
hinteger: il numero di ore che Koko ha
Restituisceinteger: la velocità di consumo minima intera, in banane all’ora, che permette di finire ogni mucchio entro h ore

Vincoli

1 ≤ piles.length ≤ 5000
1 ≤ piles[i] ≤ 10⁹
piles.length ≤ h ≤ 10⁹, 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, che rientrano nel limite. Alla velocità 4 richiedono 1, 3, 2 e 1 ore, per un totale di 7.

Per approfondire

Twin problem: Koko mangia pile intere in ordine, al massimo k banane al giorno, entro d giorni. Qual è il valore minimo di k e cosa cambia nella tua ricerca?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

La risposta è una velocità, non una posizione nell'array, e questo nasconde una ricerca binaria. Verificare una velocità richiede un passaggio sulle pile e, se la velocità k termina in tempo, lo fanno anche tutte le velocità maggiori. Quindi esegui una ricerca binaria tra le velocità da 1 fino alla pila più grande: circa 30 verifiche invece di un miliardo al massimo.

Prova ogni velocità a partire da 1

Corretto, ma non termina sui test più grandi

Intuizione

Koko non passa mai a un altro mucchio nel corso di un'ora, quindi per mangiare un mucchio di p banane servono p / k ore arrotondate per eccesso: alla velocità 4, per 10 banane servono 3 ore. Prova le velocità 1, 2, 3 e così via, e restituisci la prima per cui il tempo totale rientra in h. È la più bassa perché tutte le velocità inferiori non hanno funzionato, e il ciclo si ferma alla velocità del mucchio più grande, alla quale ogni mucchio richiede un'ora.

Con m come dimensione del mucchio più grande, si eseguono fino a m controlli su n mucchi: circa 5 × 10^12 passaggi per 5000 mucchi vicini a 10^9 e h = 5000.

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, restituisci speed.
Altrimenti aggiungi 1 a speed e 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 += 1

Ricerca binaria sulla velocità

Intuizione

Man mano che la velocità aumenta, ogni pila richiede lo stesso numero di ore o meno, quindi le risposte a «questa velocità permette di finire in tempo?» sono no, no, no e poi sì, a partire dalla risposta in poi. La ricerca binaria trova il primo sì.

Mantieni un intervallo da lo a hi che contenga sempre la risposta, iniziando da 1 e dalla pila più grande, la cui velocità richiede un'ora per pila e quindi è sufficiente. Se la velocità intermedia mid è sufficiente, la risposta è mid o una velocità inferiore, quindi imposta hi = mid. In caso contrario, anche tutte le velocità inferiori non sono sufficienti, quindi imposta lo = mid + 1. Quando lo raggiunge hi, quella è la risposta.

Nel primo esempio l'intervallo parte da 1 a 10. La velocità 5 è sufficiente, quindi diventa da 1 a 5; la velocità 3 richiede 10 ore, quindi da 4 a 5; la velocità 4 richiede 7 ore, quindi da 5 a 5.

Algoritmo

Imposta lo = 1 e hi al mucchio più grande.
Mentre lo < hi, calcola mid = lo + (hi - lo) / 2.
Conta le ore alla velocità mid: somma (pile + mid-1) / mid per ogni mucchio, usando un totale a 64 bit.
Se il totale è al massimo h, imposta hi = mid; altrimenti imposta lo = mid + 1.
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

Overflow del conteggio delle ore. A velocità 1, 5000 pile da 10^9 banane richiedono 5 × 10^12 ore, superando il limite a 32 bit, e un totale che va in overflow può far passare una velocità troppo bassa. Usa 64 bit per il conteggio oppure fermati non appena il totale supera h.
Arrotondamento per difetto. 10 / 4 dà 2, ma quella pila richiede 3 ore.
Iniziare l’intervallo da 0. In questo caso mid può essere 0 e il conteggio divide per zero.
Impostare hi = mid - 1 quando mid è sufficiente. Così si può scartare la risposta.
Iniziare con hi inferiore alla pila più grande. Quando h è uguale al numero di pile, ogni velocità inferiore non è sufficiente e la ricerca ne restituisce una.

Domande frequenti3

Qual è la complessità temporale di Koko Eating Bananas?

La ricerca binaria ha una complessità temporale di O(n log m), dove n è il numero di pile e m la pila più grande: circa log2(m) controlli, 30 quando m = 10^9, ognuno dei quali legge ogni pila una volta. Lo spazio aggiuntivo è O(1).

Quali sono il limite inferiore e il limite superiore della velocità?

Il limite superiore è il mucchio più grande: lì ogni mucchio richiede un'ora, il che è sempre sufficiente. Il limite inferiore è 1 e puoi aumentarlo fino 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 resta invariato: 10 alla velocità 4 dà 13 / 4 = 3, e 8 dà 11 / 4 = 2. Non serve la virgola mobile.

def minEatingSpeed(piles, h):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomenti

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

Output atteso