Новые остановки
Отправить решение
Решать в редакторе
Сложность:
40%
Очки:
100 (частичный балл)
Ограничение по времени:
2.0s
Ограничение по памяти:
256M
Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch
На шоссе стоят n остановок в целых точках. Можно построить не более k новых остановок, тоже в целых точках. Какое наименьшее значение может принять наибольшее расстояние между соседними остановками?
Формат ввода
В первой строке даны n и k. Во второй — координаты остановок по неубыванию.
Формат вывода
Выведите минимальное возможное наибольшее расстояние (не меньше 1).
Ограничения
2 ≤ n ≤ 10⁵, 0 ≤ k ≤ 10⁹, 0 ≤ pᵢ ≤ 10⁹.
Примеры
Пример 1
Ввод:
3 1
0 6 8
Вывод:
3
Пример 2
Ввод:
2 0
3 10
Вывод:
7
Комментарии