Algoritmos y Estructuras de Datos

Búsqueda Binaria de la Respuesta - Plantar Árboles de Forma Dispersa

Dado que se tienen n lugares posibles para plantar un árbol, se desea hacerlo con la mayor separación posible para evitar que, con el paso de los años, estos árboles interfieran entre sí. Las coordenadas de dichos lugares se proporcionan como enteros .
La tarea consiste en encontrar la distancia mínima entre t árboles, asumiendo que se han plantado de la forma más dispersa que sea posible.

Entrada

La primera línea de la entrada contiene dos números enteros n (1 ≤ n ≤ 100 000), la cantidad de lugares, y t (2 ≤ t ≤ n), el número de árboles que se deben plantar.
La siguiente línea contiene n enteros distintos separados por espacios (0 ≤ ≤ ), que representan las coordenadas de los sitios donde se puede plantar un árbol.

Salida

El programa debe imprimir la distancia mínima d entre árboles cuando se los planta de la forma más dispersa posible.

Ejemplos

Entrada
Salida
5 3 1 2 8 4 9
3

Explicación

Podemos plantar los árboles en las coordenadas 1, 4 y 9 ⇒ la distancia mínima entre ellos es 4 - 1 = 3.
 

Tutorial

Podemos resolver este problema realizando una búsqueda binaria sobre la respuesta (la distancia mínima entre árboles). En cada iteración, comprobamos si sería posible plantar los árboles con una distancia mínima dada. Para que la búsqueda binaria sobre la respuesta funcione, se deben cumplir algunos requisitos importantes:
  • Se debe poder verificar si un valor candidato satisface o no la condición del problema (en nuestro caso, verificar para una distancia mínima d si se pueden plantar los árboles de modo que queden separados al menos d unidades).
  • La función de verificación def check(x): debe devolver True si es posible satisfacer el problema con la distancia candidata x, y False en caso contrario.
  • Para valores candidatos crecientes (x distintos), el resultado de la función de verificación debe tomar una de estas dos formas:
    • 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: (imposible para los primeros valores y luego posible para valores mayores). En ese caso, se busca el primer True (es decir, el menor valor que sea válido).
- True True True True False False: (posible para valores pequeños y luego imposible para valores más grandes). En ese caso, se busca el último True (el mayor valor válido).
 
En nuestro problema, queremos plantar los árboles de la manera más dispersa posible para que la mínima distancia sea lo más grande posible. Si es posible plantar los árboles con una distancia mínima de x, definitivamente también es posible plantarlos con una distancia menor que x. Por lo tanto, nuestra función de verificación tenderá a devolver True para los valores pequeños y comenzará a devolver False a partir de un cierto punto. La meta es encontrar el último True, que corresponde a la distancia mínima más grande posible.
n, t = ...
x = sorted(x)

def check(d):
    """ Check if we can plant t trees at least d units apart """
    planted = 0               # We need to plant t trees (currently planted 0)
    prev = float('-inf')      # The coordinate of the previous tree
    for xi in x:
        if xi - prev >= d:    # If we can plant another tree at xi
            planted += 1
            prev = xi
    return planted >= t
Una vez definida la función de verificación, utilizamos la búsqueda binaria para encontrar el valor óptimo de la distancia mínima si lo que deseamos es plantar los árboles de la forma más dispersa posible:
l, r = 1, max(x)         # The answer is always in the range [l; r)
while r - l > 1:         # There is at least one element in between to consider
    mid = (l + r) // 2   # Take the middle index
    if check(mid):       # If it's possible with mid => l = mid
        l = mid
    else:                # Otherwise set r = mid
        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