Book Allocation Problem
Uno scaffale contiene libri in un ordine fisso e pages[i] è il numero di pagine del libro i. Dividi i libri tra students studenti: ogni studente riceve una sequenza contigua di libri adiacenti, almeno un libro ciascuno, e ogni libro viene assegnato esattamente a uno studente. Il carico di uno studente è il numero totale di pagine che riceve.
Restituisci il valore minimo possibile del carico più pesante. Se gli studenti sono più numerosi dei libri, restituisci -1.
Funzione
- pagesinteger-array
- il numero di pagine di ciascun libro, nell’ordine sullo scaffale
- studentsinteger
- il numero di studenti che condividono i libri
- Restituisceinteger
- il più piccolo carico massimo possibile, oppure -1 quando ci sono più studenti che libri
Vincoli
1 ≤ pages.length ≤ 50001 ≤ pages[i] ≤ 1051 ≤ students ≤ 104- Restituisci
-1quandostudents > pages.length.
Esempi
- Input
- pages = [25, 40, 15, 30, 50]students = 3
- Output
- 65
- Spiegazione
- Distribuisci
[25, 40],[15, 30]e[50]: i carichi sono 65, 45 e 50. Un limite di 64 non basta: la distribuzione dà[25],[40, 15],[30],[50], quattro studenti.
- Input
- pages = [10, 20]students = 3
- Output
- -1
- Spiegazione
- Due libri non possono dare un libro ciascuno a tre studenti, quindi la risposta è
-1.
- Input
- pages = [7, 3, 9]students = 3
- Output
- 9
- Spiegazione
- Tre libri e tre studenti: a ogni studente spetta un libro. Il più pesante è il libro di 9 pagine.
Per approfondire
Dimostra che la quota media, arrotondata per eccesso, più il libro più spesso è sempre un limite valido. Quanti controlli in meno comporta questo limite superiore su uno scaffale di libri sottili?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Invece di cercare i tagli migliori, scegli un limite di pagine. Di quanti studenti hai bisogno se nessuno può portarne più di quel numero?
Distribuisci i libri nell’ordine in cui si trovano sullo scaffale e passa allo studente successivo solo quando il libro seguente supererebbe il limite. Un limite più alto non richiede mai più studenti.
Restituisci
-1quando ci sono più studenti che libri. Altrimenti, cerca con la ricerca binaria il limite, partendo dal valore maggiore tra il libro più spesso e la quota media, fino al totale.
Soluzione
Ci sono troppi modi per tagliare lo scaffale, ma verificare un limite di pagina è semplice: distribuisci i libri nell'ordine in cui si trovano sullo scaffale, passando allo studente successivo quando un libro supererebbe il limite, e conta gli studenti. Un limite più alto non richiede mai più studenti, quindi i limiti che funzionano formano un intervallo e la ricerca binaria trova il punto in cui inizia.
Aumenta il limite di pagine una pagina alla volta
Corretto, ma non termina sui test più grandi
Intuizione
Inizia da L = max(pages), dato che qualcuno deve portare il libro più spesso, e aumenta L di una pagina alla volta finché il conteggio greedy non rientra in students. Tutti i limiti inferiori non hanno funzionato, quindi il primo che funziona è la risposta. Nel primo esempio ogni limite da 50 a 64 richiede quattro studenti, mentre 65 ne richiede tre: 16 verifiche.
La risposta può essere l'intero scaffale: uno studente e 5000 libri da 10^5 pagine significano circa 5 × 10^8 limiti, ciascuno dei quali richiede un passaggio sui 5000 libri. Nella colonna del tempo, A è la risposta e m è il libro più spesso.
Algoritmo
- Se
students > pages.length, restituisci-1. - Scrivi il conteggio greedy per un limite
L: inizia con uno studente e un carico pari a 0; quandoload + pages[i] > L, aggiungi uno studente e imposta il carico supages[i], altrimenti aggiungi il libro al carico. - Imposta
Lsul libro più spesso. - Mentre il conteggio per
Lè maggiore distudents, aggiungi 1 aL. - Restituisci
L.
def studentsNeeded(pages, limit):
count, load = 1, 0 # the first student starts with no pages
for p in pages:
if load + p > limit:
count += 1 # this book opens the next student's block
load = p
else:
load += p
return count
def allocateBooks(pages, students):
if students > len(pages):
return -1 # someone would get no book
limit = max(pages) # the thickest book has to fit somewhere
while studentsNeeded(pages, limit) > students:
limit += 1
return limitRicerca binaria sul limite della pagina
Intuizione
Il conteggio greedy è il numero minimo di studenti che qualsiasi suddivisione con L può richiedere. Confrontando uno studente alla volta con qualsiasi altra suddivisione, ogni studente greedy si ferma solo quando il libro successivo non entra, quindi termina almeno altrettanto avanti sullo scaffale. Avere meno studenti di quelli disponibili va bene: uno studente che tiene due libri può passarne uno a uno studente che non ne ha, e nessun carico aumenta.
Quindi L funziona esattamente quando il conteggio greedy è al massimo students. Qualsiasi suddivisione che funziona con L funziona anche con L+1, quindi la ricerca binaria trova il primo limite che funziona.
L'intervallo parte dal maggiore tra max(pages) e la quota media, total / students arrotondata per eccesso, poiché il carico più pesante è almeno pari a entrambi. Il limite superiore è total. Nel primo esempio l'intervallo va da 54 a 160 e la ricerca prova 107, 80, 67, 60, 64, 66 e 65.
Algoritmo
- Se
students > pages.length, restituisci-1. - Somma
totale trova il libro più spesso. Impostaloal maggiore tra il libro più spesso e(total + students - 1) / students, ehi = total. - Mentre
lo < hi, calcolamid = lo + (hi - lo) / 2. - Esegui il conteggio greedy per
mid. Se è al massimostudents, impostahi = mid; altrimenti impostalo = mid + 1. - Restituisci
lo.
def studentsNeeded(pages, limit):
count, load = 1, 0 # the first student starts with no pages
for p in pages:
if load + p > limit:
count += 1 # this book opens the next student's block
load = p
else:
load += p
return count
def allocateBooks(pages, students):
if students > len(pages):
return -1 # someone would get no book
total = sum(pages)
# no limit can be below the thickest book or below the average share
lo = max(max(pages), (total + students - 1) // students)
hi = total # one student could carry the whole shelf
while lo < hi:
mid = lo + (hi - lo) // 2
if studentsNeeded(pages, mid) <= students:
hi = mid # mid is enough, so the answer is mid or lower
else:
lo = mid + 1 # mid needs too many students
return lo
Trappole e casi limite
- Saltare il controllo
-1. Per[10, 20]e 3 studenti, il conteggio greedy con un limite di 20 è 2, quindi la ricerca restituisce 20. - Iniziare l'intervallo dal solo carico medio. Per
[1, 9]e 2 studenti, la media è 5 e, in quel caso, l'algoritmo greedy assegna il libro da 9 pagine da solo, conta 2 e restituisce 5. - Verificare che il conteggio sia esattamente
students. Per[5, 5, 5, 5, 5, 5]e 4 studenti, la risposta è 10, dove il conteggio greedy è 3. - Ordinare i libri.
[10, 1, 1, 10]con 2 studenti dà 11, ma se ordinato come[1, 1, 10, 10]dà 12.
Domande frequenti3
Il problema dell'allocazione dei libri è uguale al problema della suddivisione dell'array con la somma massima?
Sì. Entrambi suddividono un array in un numero fisso di blocchi contigui non vuoti e minimizzano la somma del blocco più grande; per risolvere entrambi si usa la stessa ricerca binaria con lo stesso controllo greedy. La versione del libro aggiunge il caso -1.
Qual è la complessità temporale del problema di allocazione dei libri?
Tempo O(n log S) e spazio aggiuntivo O(1), dove n è il numero di libri e S il numero totale di pagine. Ogni limite provato richiede una passata sui libri e la ricerca prova circa log2 S limiti: 29 su uno scaffale di 5 × 10^8 pagine.
Quando è impossibile assegnare i libri?
Solo quando ci sono più studenti che libri, dato che ogni studente ha bisogno di almeno un libro. Se ci sono abbastanza libri, qualsiasi blocco di due o più libri può cederne l'ultimo a uno studente che non ne ha, finché tutti ne hanno uno.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def allocateBooks(pages, students):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomenti
pages = [25, 40, 15, 30, 50] students = 3
Output atteso
65