Танцевальные пары


Отправить решение Решать в редакторе

Сложность: 40%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

На кружок записались n человек с ростом aᵢ. Нужно составить ровно p танцевальных пар из разных людей (каждый человек в одной паре). Разница роста в паре не должна быть большой. Какой наименьшей может быть наибольшая разница роста среди пар?

Формат ввода

В первой строке даны n и p. Во второй — рост.

Формат вывода

Выведите минимальную возможную наибольшую разницу.

Ограничения

2 ≤ n ≤ 10⁵, 1 ≤ p ≤ n/2, 1 ≤ aᵢ ≤ 10⁹.

Примеры

Пример 1

Ввод:

5 2
1 9 4 6 2

Вывод:

2
Пример 2

Ввод:

4 1
5 5 10 10

Вывод:

0

Комментарии

Еще нет ни одного комментария.