Aggressive Cows

Q: Qual è la complessità temporale di Aggressive Cows?

L'ordinamento richiede O(n log n) e la ricerca binaria O(n log D) , dove D è l'estensione delle stalle divisa per k-1 . Oltre a una copia ordinata, la memoria è O(1) .

Q: Perché la prima mucca va sempre nella stalla più a sinistra?

Scegli una qualsiasi disposizione valida e sposta la sua mucca più a sinistra nella stalla più a sinistra. Quella mucca si allontana soltanto dalle altre, quindi nessuna distanza diminuisce, e una disposizione ottimale utilizza la stalla più a sinistra.

Q: Come riconosci una ricerca binaria sulla risposta?

La domanda chiede il valore più grande o più piccolo per cui qualcosa è possibile; verificare un singolo valore è molto più facile che trovare quello ottimale, e le risposte si ribaltano una sola volta man mano che il valore cresce. Qui il valore è la distanza e la verifica consiste nel posizionamento greedy.

MedioRicerca binaria Ordinamento Greedy

+10

Una stalla ha dei recinti disposti lungo una linea retta e stalls[i] è la posizione del recinto i. Le posizioni sono tutte diverse e non sono in un ordine particolare. Devi mettere k mucche in k recinti diversi; le mucche litigano quando sono vicine, quindi vuoi che le due mucche più vicine siano il più lontane possibile.

Restituisci il valore massimo possibile della distanza minima tra due mucche qualsiasi.

Funzione

aggressiveCows(stalls: integer-array, k: integer) → integer

stallsinteger-array: le distinte posizioni degli stalli, in qualsiasi ordine
kinteger: il numero di mucche da posizionare
Restituisceinteger: la più grande distanza minima possibile tra due mucche

Vincoli

2 ≤ stalls.length ≤ 5000
0 ≤ stalls[i] ≤ 10⁹
Tutte le posizioni in stalls sono distinte.
2 ≤ k ≤ stalls.length

Esempi

Input: stalls = [10, 1, 7, 4, 15]k = 3
Output: 6
Spiegazione: Le mucche nelle posizioni 1, 7 e 15 distano rispettivamente 6 e 8. Una distanza di 7 non funziona: dopo 1, la mucca successiva va in 10 e non c’è nessuna stalla a 17 o oltre.

Per approfondire

Che cosa cambia se le bancarelle sono disposte su un cerchio, così che l’ultima bancarella in ordine sia anche vicina alla prima?

Suggerimenti

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

0 di 3 aperti

Soluzione

Scegli una distanza e chiediti: è possibile posizionare k mucche in modo che ogni coppia sia distante almeno quella misura? Basta una passata greedy sulle stalle ordinate per rispondere. La risposta passa da sì a no una sola volta man mano che la distanza aumenta, quindi la ricerca binaria trova l’ultimo sì.

Ordina, poi prova ogni intervallo a turno

Corretto, ma non termina sui test più grandi

Intuizione

Ordina le posizioni. Le due mucche più vicine sono quindi sempre vicine tra loro, perciò una distanza g funziona quando ogni coppia di mucche vicine è separata da almeno g.

Per verificare una distanza, metti una mucca nella stalla più a sinistra, poi mettine una in ogni stalla che si trovi almeno g oltre l’ultima mucca. Questa disposizione greedy permette di sistemare il maggior numero di mucche possibile. Allinea a sinistra una qualsiasi disposizione valida: la mucca i della disposizione greedy non si trova mai a destra della mucca i di quella disposizione, quindi la disposizione greedy trova una stalla per la mucca successiva non più tardi.

Una distanza pari a 1 funziona sempre, quindi prova g = 2, 3, ... e fermati alla prima distanza che permette di sistemare meno di k mucche. Nel primo esempio, con una distanza pari a 6 si sistemano 3 mucche e con una distanza pari a 7 solo 2, quindi la risposta è 6.

Con due mucche e stalle nelle posizioni 0 e 10^9, si tratta di circa 10^9 passaggi su 5000 stalle, cioè 5 × 10^12 operazioni.

Algoritmo

Ordina le posizioni.
Scrivi la verifica per una distanza g: una mucca in pos[0], poi una mucca in ogni stalla in cui pos[i] - last ≥ g, contando le mucche.
Inizia con gap = 1.
Finché la verifica per gap + 1 posiziona almeno k mucche, aggiungi 1 a gap.
Restituisci gap.

def cowsPlaced(pos, gap):
    count, last = 1, pos[0]  # the first cow takes the leftmost stall
    for p in pos[1:]:
        if p - last >= gap:
            count += 1
            last = p
    return count


def aggressiveCows(stalls, k):
    pos = sorted(stalls)
    gap = 1  # positions are distinct, so a gap of 1 always fits every cow
    while cowsPlaced(pos, gap + 1) >= k:
        gap += 1
    return gap

Ricerca binaria sull’intervallo

Intuizione

Una disposizione con ogni distanza di almeno g+1 ha anche ogni distanza di almeno g, quindi i controlli restituiscono sì, ..., sì, no, ..., no. La ricerca binaria trova l’ultimo sì.

Inizia la ricerca da lo = 1, che funziona sempre, fino a hi = l’estensione divisa per k-1, arrotondata per difetto: k mucche lasciano k-1 distanze all’interno dell’estensione, quindi la distanza minima non può essere maggiore. Un controllo superato imposta lo = mid, quindi mid deve essere arrotondato per eccesso; arrotondando per difetto, lo = 5 e hi = 6 si ripetono all’infinito.

Nel primo esempio l’estensione è 14 e k = 3, quindi hi = 7. La distanza 4 supera il controllo, la distanza 6 lo supera, la distanza 7 non lo supera e l’intervallo si chiude su 6.

Un intervallo ampio fino a 10^9 si chiude in circa 30 controlli di 5000 stalli, ovvero circa 150.000 passaggi.

Algoritmo

Ordina le posizioni.
Imposta lo = 1 e hi = (pos[n-1] - pos[0]) / (k-1), arrotondato per difetto.
Mentre lo < hi, calcola mid = lo + (hi - lo + 1) / 2.
Se il controllo greedy con mid posiziona almeno k mucche, imposta lo = mid; altrimenti imposta hi = mid - 1.
Restituisci lo.

def cowsPlaced(pos, gap):
    count, last = 1, pos[0]  # the first cow takes the leftmost stall
    for p in pos[1:]:
        if p - last >= gap:
            count += 1
            last = p
    return count


def aggressiveCows(stalls, k):
    pos = sorted(stalls)
    lo = 1  # positions are distinct, so a gap of 1 always works
    hi = (pos[-1] - pos[0]) // (k - 1)  # k-1 gaps share the whole span
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2  # round up so lo = mid always moves
        if cowsPlaced(pos, mid) >= k:
            lo = mid  # mid fits, so the answer is mid or larger
        else:
            hi = mid - 1  # mid does not fit, so the answer is smaller
    return lo

Trappole e casi limite

Saltare l'ordinamento. Sull'array non ordinato [10, 1, 7, 4, 15] con distanza 6, il controllo parte da 10, non trova stalle successive ad almeno 6 di distanza e conta una sola mucca.
Arrotondare mid per difetto mentre un passaggio imposta lo = mid. Quando hi = lo + 1, l'intervallo smette di restringersi e il ciclo non termina mai.
Verificare che ci siano esattamente k mucche. Con distanza 1, il primo esempio colloca 5 mucche, più di 3, eppure la distanza funziona; verifica count ≥ k.
Iniziare il conteggio delle mucche da 0. La mucca nella stalla più a sinistra conta, quindi il conteggio parte da 1.

Domande frequenti3

Qual è la complessità temporale di Aggressive Cows?

L'ordinamento richiede O(n log n) e la ricerca binaria O(n log D), dove D è l'estensione delle stalle divisa per k-1. Oltre a una copia ordinata, la memoria è O(1).

Perché la prima mucca va sempre nella stalla più a sinistra?

Scegli una qualsiasi disposizione valida e sposta la sua mucca più a sinistra nella stalla più a sinistra. Quella mucca si allontana soltanto dalle altre, quindi nessuna distanza diminuisce, e una disposizione ottimale utilizza la stalla più a sinistra.

Come riconosci una ricerca binaria sulla risposta?

La domanda chiede il valore più grande o più piccolo per cui qualcosa è possibile; verificare un singolo valore è molto più facile che trovare quello ottimale, e le risposte si ribaltano una sola volta man mano che il valore cresce. Qui il valore è la distanza e la verifica consiste nel posizionamento greedy.

def aggressiveCows(stalls, k):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomenti

stalls = [10, 1, 7, 4, 15]
k = 3

Output atteso