print2356. Интервалы

printИнтервалы

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Дан набор из `N` целых чисел `a_1,\ …,\ a_N`. Найти минимальную длину интервала `L`, для которой можно найти `N` целых чисел `x_1,\ …,\ x_N` таких, что каждый интервал `[\ x_i,\ x_i\ +\ L\ ]` содержит не менее `K` точек из набора `a_1,\ …,\ a_N`, в том числе `a_i`.
Первая строка ввода содержит два целых числа `N` и `K` (`1\ ≤\ K\ ≤\ N\ ≤\ 2*10^5`). Вторая строка содержит `N` целых чисел `a_1,\ ….\ a_N` (`-10^9\ ≤\ a_i\ ≤\ 10^9`).
Вывести одно целое число – минимальную длину интервала `L`.

Пример ввода

5 3
1 -2 10 5 4

Вывод для примера

6
Пояснение для примера: можно взять набор точек `x_1\ =\ -1,\ x_2\ =\ -2,\ x_3\ =\ 4,\ x_4\ =\ 0,\ x_5=0`.

37054.jpg


printРис.1

p1.jpg
loading