/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
とある世界では、今日はクリスマスイブです。
高羽氏の庭には N 本の木が植えられています。i 本目の木 (1 \leq i \leq N) の高さは 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
1, 3, 5 本目の木を飾り付けると h_{max} = 12, h_{min} = 10 となり h_{max} - h_{min} = 2 で、これが最適です。
入力例 2
5 3 5 7 5 7 7
出力例 2
0
2, 4, 5 本目の木を飾り付けると h_{max} = 7, h_{min} = 7 となり h_{max} - h_{min} = 0 で、これが最適です。
これらの入力例では木の数がそれほど多くありませんが、最大で 10 万本の木がある可能性に注意してください (ここに 10 万行の入力例を貼るわけにはいかないのです)。
Score : 300 points
Problem Statement
In some other world, today is Christmas Eve.
There are N trees planted in Mr. Takaha's garden. The height of the i-th tree (1 \leq i \leq N) is h_i meters.
He decides to choose K trees from these trees and decorate them with electric lights. To make the scenery more beautiful, the heights of the decorated trees should be as close to each other as possible.
More specifically, let the height of the tallest decorated tree be h_{max} meters, and the height of the shortest decorated tree be h_{min} meters. The smaller the value h_{max} - h_{min} is, the better. What is the minimum possible value of h_{max} - h_{min}?
Constraints
- 2 \leq K < N \leq 10^5
- 1 \leq h_i \leq 10^9
- h_i is an integer.
Input
Input is given from Standard Input in the following format:
N K h_1 h_2 : h_N
Output
Print the minimum possible value of h_{max} - h_{min}.
Sample Input 1
5 3 10 15 11 14 12
Sample Output 1
2
If we decorate the first, third and fifth trees, h_{max} = 12, h_{min} = 10 so h_{max} - h_{min} = 2. This is optimal.
Sample Input 2
5 3 5 7 5 7 7
Sample Output 2
0
If we decorate the second, fourth and fifth trees, h_{max} = 7, h_{min} = 7 so h_{max} - h_{min} = 0. This is optimal.
There are not too many trees in these sample inputs, but note that there can be at most one hundred thousand trees (we just can't put a sample with a hundred thousand lines here).