Алгоритмы и структуры данных

Бинарный поиск ответа — редкая посадка деревьев

Даны n мест, где можно посадить дерево. Вы хотите разместить деревья как можно реже, чтобы через несколько лет они не мешали друг другу. Координаты мест заданы целыми числами .
Ваша задача — найти минимальное расстояние между t деревьями при условии, что вы сажаете их как можно реже.

Входные данные

В первой строке ввода содержатся два целых числа n (1 ≤ n ≤ 100 000) — количество мест и t (2 ≤ t ≤ n) — количество деревьев, которые нужно посадить.
В следующей строке содержится n различных целых чисел (0 ≤ ≤ ), задающих координаты мест, где можно посадить дерево.

Выходные данные

Программа должна вывести минимальное расстояние d между деревьями при максимально разреженной посадке.

Примеры

Input
Output
5 3 1 2 8 4 9
3

Объяснение

Мы можем посадить деревья в координатах 1, 4 и 9 ⇒ минимальное расстояние равно 4−1 = 3.
 

Разбор задачи

Решить эту задачу можно, выполняя бинарный поиск по ответу (по минимальному расстоянию между деревьями) и проверяя на каждом шаге, возможно ли сажать деревья с заданным минимальным расстоянием. Для бинарного поиска ответа должны выполняться несколько условий:
  • Необходимо уметь проверять, удовлетворяет ли предполагаемый ответ условию задачи (в нашем случае — для заданного минимального расстояния d надо проверить, можем ли мы посадить деревья на таком расстоянии).
  • Функция проверки def check(x): должна возвращать True, если для кандидата x условие задачи выполняется, и False в противном случае.
  • По мере увеличения предполагаемого ответа (разных значений x) функция проверки будет иметь вид:
    • 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 (сначала невыполнимо для нескольких меньших чисел, затем выполнимо для больших). Тогда нужно найти первое True (наименьшее подходящее значение).
- True True True True False False (выполнимо для маленьких чисел и невыполнимо для больших). Тогда ищем последнее True (наибольшее подходящее значение).
 
В нашей задаче мы хотим максимально увеличить минимальное расстояние между деревьями, посадив их как можно реже. Если расстояние x выполнимо, то, безусловно, более плотная посадка с меньшим x тоже будет выполнимой. Следовательно, функция проверки будет иметь вид True True True True False False, и нам нужно найти последнее True (то есть максимально возможное минимальное расстояние между посаженными деревьями).
n, t = ...
x = sorted(x)

def check(d):
    """ Проверить, можем ли мы посадить t деревьев с расстоянием не менее d """
    planted = 0               # Нужно посадить t деревьев (сейчас посажено 0)
    prev = float('-inf')      # Координата предыдущего посаженного дерева
    for xi in x:
        if xi - prev >= d:    # Если можем посадить дерево в точке xi
            planted += 1
            prev = xi
    return planted >= t
Далее, с этой функцией проверки мы выполняем бинарный поиск по ответу, чтобы найти наилучшее значение минимального расстояния при максимально разреженной посадке деревьев:
l, r = 1, max(x)         # Ответ всегда находится в диапазоне [l; r)
while r - l > 1:         # Пока между l и r есть промежуточная величина
    mid = (l + r) // 2   # Берём среднее значение
    if check(mid):       # Если посадка с расстоянием mid возможна => l = 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