Подразделы

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

05/04/2025 18:59:47

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