Контест Middle Бинарный поиск спрашивают часто обновлено
Расставить зарядные станции как можно дальше друг от друга
Условие
Вдоль трассы есть n площадок с координатами x₁ … xₙ (все различны). Нужно поставить k зарядных станций на разные площадки так, чтобы минимальное расстояние между соседними станциями было как можно больше. Выведите это максимальное минимальное расстояние.
Ввод: в первой строке n и k (2 ≤ k ≤ n ≤ 2500), во второй n различных целых координат (0 ≤ xᵢ ≤ 10⁹), не обязательно упорядоченных.
Вывод: одно число.
Пример 1
Ввод:
5 3
1 2 8 4 9
Вывод:
3
Пример 2
Ввод:
2 2
0 1000000000
Вывод:
1000000000
Как подойти
Подсказки: 2
- Если можно расставить с расстоянием d, то можно и с меньшим.
- Проверка для фиксированного d: жадно ставьте станцию на первую подходящую площадку.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.