Algorithmes et Structures de Données

Recherche binaire de la réponse – Planter des arbres de manière espacée

Étant donné n emplacements où vous pouvez planter un arbre, vous souhaitez les planter de la façon la plus espacée possible afin d’éviter qu’ils ne se gênent mutuellement dans quelques années. Les coordonnées de ces emplacements sont données par des entiers .
Votre tâche est de déterminer la distance minimale entre t arbres si vous les plantez en les espaçant le plus possible.

Entrée

La première ligne de l’entrée contient deux entiers n (1 ≤ n ≤ 100 000), le nombre d’emplacements, et t (2 ≤ t ≤ n), le nombre d’arbres à planter.
La ligne suivante contient n entiers distincts séparés par un espace (0 ≤ ≤ ), qui correspondent aux coordonnées des emplacements où planter un arbre.

Sortie

Le programme doit afficher la distance minimale d entre les arbres lorsqu’ils sont plantés de la manière la plus espacée possible.

Exemples

Entrée
Sortie
5 3 1 2 8 4 9
3

Explication

On peut planter les arbres aux coordonnées 1, 4 et 9 ⇒ la distance minimale est 4-1 = 3.
 

Tutoriel

Nous pouvons résoudre ce problème en effectuant une recherche binaire sur la réponse (la distance minimale entre arbres) et en vérifiant à chaque étape s’il est possible de planter les arbres avec au moins cette distance. Certaines conditions sont nécessaires pour que ce type de recherche soit possible :
  • On doit être capable de vérifier si un candidat de réponse satisfait ou non l’énoncé du problème (dans notre cas, vérifier si, pour une distance minimale d, il est possible de planter les arbres de telle façon qu’ils soient à au moins d unités de distance les uns des autres).
  • La fonction de vérification def check(x): doit renvoyer True si l’on peut répondre à l’énoncé avec le candidat x, et False sinon.
  • Pour des valeurs croissantes du candidat (différentes valeurs de x), la valeur de la fonction de vérification doit ressembler à l’un des deux schémas suivants :
    • 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 (impossible pour les premières valeurs, puis possible pour les plus grandes). On cherche alors la première occurrence de True.
- True True True True False False (possible pour les petites valeurs puis impossible pour les plus grandes). On cherche alors la dernière occurrence de True.
 
Dans notre cas, nous voulons planter les arbres le plus largement possible. Nous souhaitons donc que la distance minimale soit aussi grande que possible. Si c’est possible de planter les arbres avec une distance minimale de x, alors il est nécessairement possible de les planter de façon plus dense (avec une distance plus petite), donc les valeurs de la fonction de vérification auront la forme True True True True False False. Nous chercherons donc la dernière occurrence de True dans cette liste (c’est-à-dire la plus grande distance minimale qui fonctionne).
n, t = ...
x = sorted(x)

def check(d):
    """ Vérifie s'il est possible de planter t arbres en les espaçant d'au moins d unités """
    planted = 0
    prev = float('-inf')
    for xi in x:
        if xi - prev >= d:
            planted += 1
            prev = xi
    return planted >= t
Une fois cette fonction de vérification écrite, on peut effectuer la recherche binaire pour trouver la meilleure valeur de distance minimale :
l, r = 1, max(x)
while r - l > 1:
    mid = (l + r) // 2
    if check(mid):
        l = mid
    else:
        r = mid

print(l)
 

Constraints

Time limit: 4 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue