Chocolate Distribution Problem

Q: Qual è la complessità temporale del problema della distribuzione del cioccolato?

L’ordinamento richiede O(n log n) e lo scorrimento della finestra di m pacchetti richiede O(n) , quindi il tempo totale è O(n log n) . Lo spazio aggiuntivo è O(n) per una copia ordinata, oppure O(1) oltre a quello richiesto dall’ordinamento stesso se ordini l’input sul posto.

Q: Il problema della distribuzione del cioccolato è un problema di finestra scorrevole?

Sì, una finestra di dimensione fissa sui pacchetti ordinati. A differenza di una finestra con somma cumulativa, non c'è nulla da aggiornare mentre si sposta: la differenza di ogni finestra si ottiene sottraendo il primo pacchetto all'ultimo.

Q: È possibile risolvere il problema della distribuzione del cioccolato senza ordinare?

Le dimensioni qui sono al massimo 10^5 , quindi un ordinamento per conteggio le ordina in tempo O(n + 10^5) e lo stesso ragionamento vale. Con dimensioni senza limiti, i soli confronti non possono fare meglio di O(n log n) : con m = 2 la risposta è 0 esattamente quando due pacchetti sono uguali, e rilevare un duplicato richiede quel numero di confronti nel caso peggiore.

FacileOrdinamento Finestra scorrevole

+10

Hai alcuni pacchetti di cioccolatini e packets[i] indica il numero di cioccolatini nel pacchetto i. Ognuno degli m studenti riceve esattamente un pacchetto, quindi vengono distribuiti m pacchetti diversi. Sceglili in modo che la differenza tra il pacchetto più grande e quello più piccolo distribuiti sia la minore possibile.

Scrivi una funzione chiamata minDifference che restituisca la differenza minima possibile.

Funzione

minDifference(packets: integer-array, m: integer) → integer

packetsinteger-array: il numero di cioccolatini in ciascun pacchetto
minteger: il numero di studenti, ciascuno dei quali riceve un pacchetto
Restituisceinteger: la differenza più piccola possibile tra il pacchetto più grande e quello più piccolo distribuiti

Vincoli

2 ≤ m ≤ packets.length ≤ 10⁴
1 ≤ packets[i] ≤ 10⁵
Due pacchetti possono contenere lo stesso numero di cioccolatini.

Esempi

Input: packets = [9, 3, 15, 7, 11, 4]m = 3
Output: 4
Spiegazione: In ordine, i pacchetti sono 3, 4, 7, 9, 11 e 15. Sia 3, 4, 7 sia 7, 9, 11 hanno una differenza di 4, e non ci sono tre pacchetti più vicini tra loro.

Input: packets = [8, 1, 5]m = 3
Output: 7
Spiegazione: Ci sono tre studenti e tre pacchetti, quindi ogni pacchetto viene distribuito e la differenza è 8 - 1 = 7.

Suggerimenti

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

0 di 3 aperti

Soluzione

Provare ogni gruppo di m pacchetti è troppo lento. La scelta migliore è sempre costituita da m pacchetti consecutivi dopo averli ordinati. Quindi ordinali una volta sola: la risposta è la differenza minima tra gli elementi di qualsiasi finestra di m pacchetti consecutivi, trovata in un'unica passata.

Correggi il pacchetto più piccolo

Corretto, ma non termina sui test più grandi

Intuizione

Fissa il pacchetto più piccolo che distribuisci, low. Per mantenere piccolo quello più grande, prendi i m-1 pacchetti più piccoli che contengono almeno low. La differenza è quindi il m-esimo pacchetto più piccolo tra quelli che contengono almeno low, meno low. Prova ogni pacchetto come low, salta quelli per cui ci sono meno di m pacchetti di dimensioni pari o superiori e mantieni la differenza più piccola.

Ognuna delle n scelte filtra e ordina fino a n pacchetti: O(n² log n). Con n = 10^4 dimensioni diverse, i soli ordinamenti comportano circa 6 × 10^8 confronti.

Algoritmo

Imposta best a un valore che nessuna risposta può superare.
Per ogni pacchetto low, raccogli tutti i pacchetti che contengono almeno low cioccolatini e ordinali.
Se ce ne sono almeno m, l’m-esimo più piccolo meno low è un candidato.
Conserva il candidato più piccolo in best e restituiscilo.

def minDifference(packets, m):
    best = max(packets) - min(packets)  # no gap can be wider than this
    for low in packets:
        # The packets that could go out alongside low, smallest first (low is one of them).
        bigger = sorted(x for x in packets if x >= low)
        if len(bigger) >= m:
            best = min(best, bigger[m - 1] - low)
    return best

Ordina e fai scorrere una finestra di m pacchetti

Intuizione

In ordine crescente, una finestra sizes[i..i+m-1] ha il pacchetto più piccolo all’inizio e quello più grande alla fine, quindi la sua differenza è sizes[i+m-1] - sizes[i].

La scelta migliore può sempre essere una finestra. Se una scelta salta un pacchetto che si trova tra quello più piccolo e quello più grande, sostituisci quello più grande con quel pacchetto. Quello più piccolo resta invariato e quello più grande può solo diminuire, quindi la differenza non aumenta mai. Ripeti finché non rimangono spazi.

Nel primo esempio, le finestre di tre elementi danno 4, 5, 4 e 6, quindi la risposta è 4. L’ordinamento costa O(n log n) e lo scorrimento O(n).

Algoritmo

Ordina i pacchetti in ordine crescente in sizes.
Imposta best su sizes[m-1] - sizes[0], la prima finestra.
Per ogni indice iniziale i da 1 a n-m, confronta sizes[i+m-1] - sizes[i] con best e conserva il valore più piccolo.
Restituisci best.

def minDifference(packets, m):
    sizes = sorted(packets)
    best = sizes[m - 1] - sizes[0]
    # The window sizes[i..i+m-1] holds m packets; its first is the smallest, its last the largest.
    for i in range(1, len(sizes) - m + 1):
        best = min(best, sizes[i + m - 1] - sizes[i])
    return best

Trappole e casi limite

Terminare la finestra in i+m invece che in i+m-1, il che misura m+1 pacchetti.
Fermarsi una finestra troppo presto. Gli indici di partenza vanno da 0 a n-m inclusi. Per [1, 10, 20, 21] con m = 2, un ciclo con i < n-m non rileva l'unica differenza pari a 1.
Saltare l'ordinamento. In [9, 3, 15, 7, 11, 4] i primi tre pacchetti differiscono di 12, mentre la risposta è 4.
Misurare solo la prima finestra. I m pacchetti più piccoli sono una possibile scelta, ma il gruppo migliore può iniziare ovunque.
Ordinare i numeri come testo. In JavaScript, sort() senza un comparatore mette 100000 prima di 9.

Domande frequenti3

Qual è la complessità temporale del problema della distribuzione del cioccolato?

L’ordinamento richiede O(n log n) e lo scorrimento della finestra di m pacchetti richiede O(n), quindi il tempo totale è O(n log n). Lo spazio aggiuntivo è O(n) per una copia ordinata, oppure O(1) oltre a quello richiesto dall’ordinamento stesso se ordini l’input sul posto.

Il problema della distribuzione del cioccolato è un problema di finestra scorrevole?

Sì, una finestra di dimensione fissa sui pacchetti ordinati. A differenza di una finestra con somma cumulativa, non c'è nulla da aggiornare mentre si sposta: la differenza di ogni finestra si ottiene sottraendo il primo pacchetto all'ultimo.

È possibile risolvere il problema della distribuzione del cioccolato senza ordinare?

Le dimensioni qui sono al massimo 10^5, quindi un ordinamento per conteggio le ordina in tempo O(n + 10^5) e lo stesso ragionamento vale. Con dimensioni senza limiti, i soli confronti non possono fare meglio di O(n log n): con m = 2 la risposta è 0 esattamente quando due pacchetti sono uguali, e rilevare un duplicato richiede quel numero di confronti nel caso peggiore.

def minDifference(packets, m):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomenti

packets = [9, 3, 15, 7, 11, 4]
m = 3

Output atteso