Чекпоинты на арене: максимальный минимальный разрыв

В игре проводят турнир на длинной прямой арене. По линии уже размечены возможные места для чекпоинтов — каждое место задаётся координатой.

Организатор хочет поставить ровно k чекпоинтов так, чтобы игрокам было «не скучно»: самый маленький промежуток между соседними выбранными чекпоинтами (если смотреть слева направо) должен быть как можно больше.

Нужно узнать, какой максимальной может быть эта величина.

Важно: координаты могут повторяться. Все числа целые. Значения координат могут не помещаться в 32-битный тип (как на ВсОШ), используйте 64-битные целые; в Python это не проблема.

Формат ввода

Первая строка: два целых числа n и k (2 ≤ k ≤ n ≤ 3000).

Вторая строка: n целых чисел x1, x2, ..., xn — координаты (0 ≤ xi ≤ 10^9).

Формат вывода

Выведите одно целое число — максимально возможное значение минимального расстояния между соседними выбранными чекпоинтами.

Ограничения

• 2 ≤ k ≤ n ≤ 3000
• 0 ≤ xi ≤ 10^9
• координаты могут повторяться
• время: 1 c, память: 256 МБ

Пример

Ввод:

5 3
1 2 8 4 9

Вывод:

3

Пояснение: можно выбрать чекпоинты в точках 1, 4 и 8. Тогда минимальный разрыв между соседними равен 3.

Ключевое наблюдение: если мы хотим, чтобы минимальный разрыв между соседними выбранными чекпоинтами был хотя бы d, то вопрос сводится к проверке «влезет ли k точек с шагом не меньше d». Это свойство монотонное: если для какого-то d получилось, то для всех меньших тоже получится. Значит, можно делать бинарный поиск по ответу.

Почему жадный метод работает для проверки: чтобы поставить как можно больше чекпоинтов при фиксированном d, выгодно каждый следующий ставить максимально слева (в первую подходящую позицию). Если даже так не набрали k, то никакой другой выбор не поможет.

План:

• Отсортируй координаты.
• Заведи функцию can(d):
• поставь первый чекпоинт в a[0], cnt = 1, last = a[0];
• иди слева направо и ставь новый, если x - last >= d (обновляй last, увеличивай cnt);
• верни True, если cnt >= k.
• Бинарным поиском найди максимальное d в диапазоне от 0 до a[-1] - a[0].
• В середине бери mid = (lo + hi + 1) // 2 и решай, сдвигать lo или hi.

Сложность: сортировка O(n log n), каждая проверка O(n), бинарный поиск ~30 шагов, итого O(n log n + n log C).

Частая ошибка: забыть про +1 в середине ((lo+hi+1)//2) — тогда при lo+1=hi можно зациклиться. Также координаты могут повторяться, поэтому ответ иногда равен 0 — не отсекай этот случай.