Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2356. Интервалы
Бинарный поискСканирование, метод двух указателей
Олимпиадные задачи на русском языке
| 14/10/2017 | Открытые личные соревнования по спортивному программированию (H) |
| 03/07/2023 | Лето 2023-4 простые (D) |
Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение 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`.
