解题思路

先将所有可选站位坐标按从小到大排序。问题就转化为：

从 $K$ 个不同坐标中选出 $N$ 个，使得任意相邻两名偶像之间距离的最小值尽可能大，求这个最大值。

这就是经典的“二分答案 + 贪心判定”问题，也常叫作“最大化最小值”问题。

相关算法

题目内容

充满梦想与希望的虚拟空间"月读"即将举办一场名为“辉夜盛典"的演出，舞台导演多多正在为终幕的虚拟偶像大集合节目安排站位，共有 $N$ 位虚拟偶像参与该节目，舞台上共设有 $K$ 个可用的投影站位，其坐标分别为 $x_i$。

如果两名虚拟偶像站位太近，全息投影的动作捕捉范围以及演出特效就会发生重叠，导致演出出现“穿模事故。多多将一套站位方案的稳定程度定义为：任意两名虚拟偶像之间距离的最小值。请你帮多多计算一下，所有站位方案的稳定程度最大可以是多少?

输入描述

第一行为一个整数 $T$ ，表示共有 $T$ 个测试数据 $(1<=T<=10)$

每组测试数据:

第一行两个整数 $K，N$，其中 $K$ 舞台的可用投影站位数， $N$ 表示参与演出的虚拟偶像总人数 $(2<=N<=K<=100000)$

第二行是 $K$ 个整数，表示投影站位序列，其中每个 $x_i$ 表示站位坐标 $(1<=x_i <= 10^9)$

输出描述

每组数据输出一个结果，每个结果占一行

补充说明

对于 $20$% 的数据有:$2<=K<=1000,1<=x_i<=10^6$

对于 $100$% 的数据有:$2<=K<=100000,1<=x_i<=10^9$

对于同一组测试数据，所有 $x_i$ 两两不同

样例1

输入

1
3 2
1 6 8

输出

7

说明

共有 $3$ 个站位，需要安排 $2$ 名偶像

$2$ 名虚拟偶像安排在站位坐标 $1、8$，可获得最大稳定程度 $7$

样例2

输入

1
6 4
24 3 42 15 7 30

输出

12

说明

共有 $6$ 个站位，需要安排 $4$ 名偶像。

最优方案是将 $4$ 名偶像安排在站位坐标 $3、42、15、30$

此时任意两名相邻偶像之间的距离分别为 $12(15-3)、15(30-15)、12(42-30)$，可获得最大稳定程度 $12$

样例3

输入

1
5 3
10000 10 20000 1 19999

输出

9999

说明

共有 $5$ 个站位，需要安排 $3$ 名偶像

$3$ 名虚拟偶像安排在站位坐标 $10000、1、19999$ 时任意两名相邻偶像之间的距离分别为 $9999(10000-1)、9999(19999-10000)$，可获得最大稳定程度 $9999$ (安排在 $10000、1、20000$ 也是最优解之一)