D. 挑选风铃

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

共有 n 个风铃悬挂在屋檐下,每个风铃都能发出一定音调的声音。从左到右给风铃从 1 n 编号,第 i 个风铃的音调是 a_i

为了表达内心的思念,扶苏决定在 n 个的风铃中取出 m 个,送给远方的朋友。

请你找到最小的整数 \varepsilon ,使得存在一种方案,能够从 n 个风铃中挑出 m 个,设挑出风铃的音调为 b_1, b_2, \dots b_m ,满足对任意的 1 \leq i, j \leq m ,都有 |b_i - b_j| \leq \varepsilon

输入格式

输入格式

第一行是两个整数,表示风铃的个数 n 和挑选出风铃的个数 m
第二行有 n 个整数,表示每个风铃的音调。第 i 个整数表示 a_i

输出格式

输出格式

输出一行一个整数,表示最小的 \varepsilon

样例

样例 #1

样例输入 #1

5 3
1 2 3 4 5

样例输出 #1

2

样例 #2

样例输入 #2

6 4
1 7 8 3 4 6

样例输出 #2

4

数据范围与提示

数据规模与约定

  • 10\% 的数据, m = 2
  • 另有 10\% 的数据, m = n
  • 40\% 的数据, n \leq 5
  • 60\% 的数据,保证对所有的 2 \leq i \leq n ,满足 a_{i - 1} \leq a_i ,即 a_i 单调不降。
  • 80\% 的数据, n \leq 10^3
  • 100\% 的数据, 2 \leq m \leq n \leq 10^5 1 \leq a_i \leq 10^9

样例 2 解释

一种选择的方案是选择第 2,4,5,6 四个风铃,音调依次为 7,3,4,6 。可以得到对任何的 1 \leq i, j\leq 4 ,都有 |b_i - b_j| \leq 4

另一种方案是选择第 2,3,5,6 四个风铃,同样计算得到的 \varepsilon 4