Подразделы

Другие разделы

Дата и время

16/11/2024 15:18:47

Авторизация

2356. Интервалы

Интервалы

Ограничения: время – 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

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

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

14/10/2017	Открытые личные соревнования по спортивному программированию (H)
03/07/2023	Лето 2023-4 простые (D)
01/07/2024	Лето 2024-4 простые (D)