Ricerca binaria sulla risposta – Piantare alberi in modo sparso

Hai a disposizione n posizioni in cui puoi piantare un albero e desideri farlo nella maniera più diradata possibile, in modo che in futuro gli alberi non si interferiscano tra loro. Le coordinate di queste posizioni sono fornite come interi .

Il tuo compito è trovare la distanza minima tra t alberi se li pianti in modo da massimizzare lo spazio tra di loro.

Input

La prima riga dell’input contiene due interi n (1 ≤ n ≤ 100 000), il numero di posizioni disponibili, e t (2 ≤ t ≤ n), il numero di alberi da piantare.

La riga successiva contiene n interi distinti separati da spazio (0 ≤ ≤ ), che rappresentano le coordinate delle posizioni in cui è possibile piantare un albero.

Output

Il programma deve stampare la distanza minima d tra gli alberi quando sono piantati in modo più diradato possibile.

Esempi

Input	Output
5 3 1 2 8 4 9	3

Spiegazione

Possiamo piantare gli alberi alle coordinate 1, 4 e 9. In questo caso, la distanza minima è 4−1 = 3.

Tutorial

È possibile risolvere questa sfida eseguendo una ricerca binaria sulla risposta (cioè sulla distanza minima tra alberi) e verificando a ogni iterazione se è possibile piantare gli alberi con una data distanza minima. Ci sono alcune condizioni importanti affinché la ricerca binaria sulla risposta sia fattibile:

Deve essere possibile verificare se una certa risposta candidata soddisfa i requisiti del problema (nel nostro caso, controllare se, data una distanza minima d, è possibile piantare tutti gli alberi in modo che siano almeno d unità separati tra loro).

La funzione di controllo def check(x): deve restituire True se è possibile soddisfare il problema con la risposta candidata x, altrimenti False.

Per valori crescenti della risposta candidata (diversi valori di x), la funzione di controllo dovrebbe comportarsi come:

False False False True True (impossible for the first several numbers and then possible for larger ones). In this case, we’re looking for the first True (the smallest valid value).
True True True True False False (possible for small numbers and impossible for larger ones). In this case, we’re looking for the last True (the largest valid value).

In our case, we would like to plant the trees as sparsely as possible. So, we would like the minimum distance to be as large as possible. If it’s possible to plant trees with a minimum distance of x, then it’s definitely possible to plan them denser and get a smaller x. Therefore, in our case, the values of the checking function will be True True True True False False and we aim to find the last True in this list (the largest (most sparse) minimal distance between the planted trees).

- False False False True True (impossibile per i primi valori e poi possibile per quelli più grandi) quando cerchiamo il primo True (il più piccolo valore valido).

- True True True True False False (possibile per i numeri piccoli e impossibile per quelli più grandi) quando cerchiamo l’ultimo True (il valore più grande che resta valido).

Nel nostro caso, vogliamo piantare gli alberi nel modo più diradato possibile. Perciò desideriamo che la distanza minima sia la più grande possibile. Se è possibile piantare gli alberi con una distanza minima di x, allora sarà sicuramente possibile piantarli anche in modo più denso, con una distanza minore di x. Quindi, in questo contesto, la funzione di controllo assumerà l’andamento True True True True False False, e noi puntiamo a individuare l’ultimo True nell’intervallo (la distanza minima più grande).

n, t = ...
x = sorted(x)

def check(d):
    """ Verifica se possiamo piantare t alberi con almeno d unità di distanza """
    planted = 0               # Abbiamo bisogno di piantare t alberi (attualmente ne abbiamo piantati 0)
    prev = float('-inf')      # La coordinata del precedente albero
    for xi in x:
        if xi - prev >= d:    # Se possiamo piantare un altro albero a xi
            planted += 1
            prev = xi
    return planted >= t

Una volta definita la funzione di controllo, possiamo eseguire la ricerca binaria sulla risposta per trovare il valore ottimale per la distanza minima, in modo da piantare gli alberi nel modo più diradato possibile:

l, r = 1, max(x)         # La risposta è sempre nel range [l; r)
while r - l > 1:         # C’è almeno un valore intermedio da verificare
    mid = (l + r) // 2   # Determina il valore centrale
    if check(mid):       # Se è possibile con mid => l = mid
        l = mid
    else:                # Altrimenti r = mid
        r = mid

print(l)

Ricerca binaria sulla risposta – Piantare alberi in modo sparso

Input

Output

Esempi

Spiegazione

Tutorial

Constraints

To check your solution you need to sign in

Sign in to continue