AT_abc115_c [ABC115C] Christmas Eve

题目描述

在某个世界里，今天是圣诞节前夜。

高羽先生的庭院里种植着 $N$ 棵树。第 $i$ 棵树的高度为 $h_i$ 米。

他打算从这些树中选出 $K$ 棵进行装饰。为了营造更美丽的景象，他希望选择高度尽可能接近的树进行装饰。

更具体地说，假设被装饰的树中最高的高度为 $h_{max}$ 米，最低的高度为 $h_{min}$ 米，则 $h_{max} - h_{min}$ 越小越好。请问 $h_{max} - h_{min}$ 的最小值是多少？

输入格式

输入以以下格式从标准输入给出。

$N$ $K$
$h_1$
$h_2$
$\vdots$
$h_N$

输出格式

请输出 $h_{max} - h_{min}$ 可能取得的最小值。

样例 1

输入

5 3
10
15
11
14
12

输出

2

样例 2

输入

5 3
5
7
5
7
7

输出

0

说明/提示

限制条件

• $2 \leq K < N \leq 10^5$
• $1 \leq h_i \leq 10^9$
• $h_i$ 是整数。

样例解释 1

如果选择第 $1, 3, 5$ 棵树进行装饰，则 $h_{max} = 12, h_{min} = 10$，因此 $h_{max} - h_{min} = 2$，这是最优解。

样例解释 2

如果选择第 $2, 4, 5$ 棵树进行装饰，则 $h_{max} = 7, h_{min} = 7$，因此 $h_{max} - h_{min} = 0$，这是最优解。请注意，虽然这些输入样例中的树的数量不多，但树的数量最多可能达到 $10$ 万棵（我们无法在这里贴出 $10$ 万行的输入样例）。

由 ChatGPT 4.1 翻译