#CW2. 最远间距(dis)

最远间距(dis)

题目描述

给定一条数轴上的 nn 个候选位置,其坐标分别为 a1,a2,…,ana_1, a_2, \ldots, a_n。

现在需要从这 nn 个位置中恰好选出 mm 个位置。

设选出的 mm 个位置中,任意两个位置之间的距离最小值为 dd。请你选择一种方案,使 dd 尽可能大,并求出这个最大值。

换句话说,需要从所有可行的选择方案中,最大化所选位置之间的最小距离。

输入格式

第一行包含两个整数 nn 和 mm,分别表示候选位置的数量和需要选择的位置数量,其中:

  • 2≤n≤1052 \le n \le 10^5;
  • 2≤m≤n2 \le m \le n。

第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_n,表示各候选位置的坐标,其中 0≤ai≤1060 \le a_i \le 10^6。

输出格式

输出一行一个整数,表示选择 mm 个位置后,能够达到的最大最小距离。

样例 1 输入

5 3
2 3 9 6 11

样例 1 输出

4

样例 1 解释

选择 2,6,112, 6, 11 三个点。

样例 2 输入

4 3
1 4 9 10

样例 2 输出

3

数据范围

对于所有测试数据,保证:

  • 2≤n≤1052 \le n \le 10^5;
  • 2≤m≤n2 \le m \le n;
  • 0≤ai≤1060 \le a_i \le 10^6。
测试点 n≤n \le m≤m \le 特殊性质
1∼41 \sim 4 2020 nn 无
5∼65 \sim 6 10001000 ai≤1000a_i \le 1000
7∼107 \sim 10 无
11∼1211 \sim 12 10510^5 ai=ia_i = i
13∼1513 \sim 15 33 无
16∼2016 \sim 20 nn