分数: 300 点
问题陈述
在另一个世界,今天是平安夜。
有 N 高叶先生花园里种植的树木。的高度 i第棵树 (1 \leq i \leq N) is h_i 米。
他决定选择 K 这些树上的树,并用电灯装饰它们。为了使景色更加美丽,装饰树的高度应尽可能接近。
更具体地说,让最高的装饰树的高度为 h_{max} 米,最短装饰树的高度为 h_{min} 米。值越小 h_{max} - h_{min} 是越好。的最小可能值是多少 h_{max} - h_{min}?
约束
- 2 \leq K < N \leq 10^5
- 1 \leq h_i \leq 10^9
- h_i 是一个整数。
输入
输入由标准输入按以下格式给出:
N K h_1 h_2 : h_N
输出
打印最小可能值 h_{max} - h_{min}.
示例输入 1
5 3 10 15 11 14 12
示例输出 1
2
如果我们装饰第一棵、第三棵和第五棵树, h_{max} = 12, h_{min} = 10 so h_{max} - h_{min} = 2。这是最佳的。
示例输入 2
5 3 5 7 5 7 7
示例输出 2
0
如果我们装饰第二棵、第四棵和第五棵树, h_{max} = 7, h_{min} = 7 so h_{max} - h_{min} = 0。这是最佳的。
这些样本输入中没有太多的树,但请注意,最多可以有十万棵树(我们只是不能在这里放置十万行的样本)。