← 返回题目列表

AtCoder · abc115_c

C. 平安夜

中文机器翻译题面 查看原题

分数: 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。这是最佳的。

这些样本输入中没有太多的树,但请注意,最多可以有十万棵树(我们只是不能在这里放置十万行的样本)。