g5-09162. 讲座座位 未做

报告厅里一排座位沿数轴摆放,第 $i$ 个座位位于坐标 $x_i$,坐标可能重复,输入顺序任意。主办方要从中选出恰好 $k$ 个座位安排嘉宾就座,希望任意相邻两位嘉宾坐得尽量远,也就是最大化相邻被选座位间距的最小值。请输出这个最小间距的最大值。

第一行两个整数 $n,k$。
第二行 $n$ 个整数 $x_i$,表示各座位坐标,顺序任意。

一行一个整数,表示最大化的相邻被选座位最小间距。

排序后坐标为 $1,2,4,8,9$。选 $\{1,4,8\}$ 三个座位,相邻间距为 $3,4$,最小值 $3$。再验证 $4$:从最左的 $1$ 出发,下一个间距不小于 $4$ 的座位是 $8$,再往后没有,只能选出 $2$ 个座位,不足 $3$ 个,不可行。故答案为 $3$。

$2\le k\le n\le 10^5$;$0\le x_i\le 10^9$。