Christmas Eve

题目描述

在另一个世界，今天是平安夜。 高桥先生的花园里种了 $N$ 棵树。第 $i$ 棵树 $(1 \leq i \leq N)$ 的高度为 $h_i$ 米。 他决定从这些树中选择 $K$ 棵并用彩灯装饰。为了使景观更美，所选装饰树的高度应尽可能接近。 更具体地，设被装饰的最高树的高度为 $h_{max}$ 米，最矮树的高度为 $h_{min}$ 米。$h_{max} - h_{min}$ 越小越好。求 $h_{max} - h_{min}$ 的最小可能值。

输入格式

输入通过标准输入给出，格式如下： $N$ $K$ $h_1$ $h_2$ : $h_N$

输出格式

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

5 3
10
15
11
14
12

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、3 和 5 棵树，$h_{max} = 12, h_{min} = 10$，所以 $h_{max} - h_{min} = 2$。这是最优的。
如果我们装饰第 2、4 和 5 棵树，$h_{max} = 7, h_{min} = 7$，所以 $h_{max} - h_{min} = 0$。这是最优的。 这些样例输入中的树不多，但注意最多可能有十万棵树（我们无法在这里放一个有十万行的样例）。

标签: AtCoder|abc115C

来源

AtCoder|abc115C