题目描述
给定一条数轴上的 n 个候选位置,其坐标分别为 a1,a2,…,an。
现在需要从这 n 个位置中恰好选出 m 个位置。
设选出的 m 个位置中,任意两个位置之间的距离最小值为 d。请你选择一种方案,使 d 尽可能大,并求出这个最大值。
换句话说,需要从所有可行的选择方案中,最大化所选位置之间的最小距离。
输入格式
第一行包含两个整数 n 和 m,分别表示候选位置的数量和需要选择的位置数量,其中:
- 2≤n≤105;
- 2≤m≤n。
第二行包含 n 个整数 a1,a2,…,an,表示各候选位置的坐标,其中 0≤ai≤106。
输出格式
输出一行一个整数,表示选择 m 个位置后,能够达到的最大最小距离。
样例 1 输入
5 3
2 3 9 6 11
样例 1 输出
4
样例 1 解释
选择 2,6,11 三个点。
样例 2 输入
4 3
1 4 9 10
样例 2 输出
3
数据范围
对于所有测试数据,保证:
- 2≤n≤105;
- 2≤m≤n;
- 0≤ai≤106。
| 测试点 |
n≤ |
m≤ |
特殊性质 |
| 1∼4 |
20 |
n |
无 |
| 5∼6 |
1000 |
ai≤1000 |
| 7∼10 |
无 |
| 11∼12 |
105 |
ai=i |
| 13∼15 |
3 |
无 |
| 16∼20 |
n |