最大化最小距离

题目描述

数轴上有 n 个可选位置，位置坐标互不相同。你需要从中选择 k 个位置。

把选中的位置从小到大排列后，定义相邻两个已选位置之间距离的最小值为本次方案的得分。

请最大化这个最小距离，并输出最大得分。

输入格式

第一行两个整数 n、k。

第二行包含 n 个互不相同的位置坐标，输入顺序不一定有序。

输出格式

输出能够得到的最大最小距离。

5 3
1 2 8 4 9

3

数据范围

• 1 <= k <= n <= 200000
• 0 <= position[i] <= 10^18
• 坐标互不相同