神之子的花海布局

题目背景

立海大的网球场边，被称为“神之子”的幸村精市（Yukimura Seiichi）意外邂逅了一位降临人间的可爱小天使。她纯洁无瑕，身后有着洁白的羽翼。向来以剥夺五感、冷酷霸气著称的幸村，在那一瞬间，心跳漏了一拍——他恋爱了。

为了向这位小天使表达心意，幸村决定利用他那完美的控球能力，在网球场上用 $M$ 朵象征着“奇迹”的蓝色鸢尾花摆出一个绝美的阵列。

球场上是一条笔直的底线，底线上有 $N$ 个可以放置花朵的定点，坐标分别为 $x_1, x_2, \dots, x_N$。

幸村认为，完美的布局需要有“呼吸感”。为了让整个花海看起来最为壮观且充满神性，他希望任意两朵花之间的距离都尽可能远。

具体来说，幸村希望最大化 “最近的两朵花之间的距离”。 请你帮助这位陷入爱河的部长计算出，在这个最佳布局下，最近的两朵花之间的距离是多少？

题目描述

给定 $N$ 个整数坐标 $x_1, x_2, \dots, x_N$，表示底线上可用的位置。 你需要从中选择 $M$ 个位置来放置花朵。 目标是让这 $M$ 朵花中，任意两朵花之间距离的最小值尽可能大。 输出这个最大的“最小值”。

输入格式

第一行包含两个整数 $N$ 和 $M$ ($2 \le M \le N \le 10^5$)，分别表示可用位置的数量和需要放置的花朵数量。 第二行包含 $N$ 个整数 $x_i$ ($0 \le x_i \le 10^9$)，表示每个位置的坐标。

输出格式

输出一个整数，表示最大的最小距离。

样例数据

输入 #1

5 3
1 2 8 4 9

输出 #1

3

输入 #2

6 4
1 10 15 20 26 30

输出 #2

9

样例解释 #1

坐标点排序后为：1, 2, 4, 8, 9。 我们需要选 3 个点。

• 方案 A：选 1, 4, 8。距离分别为 $4-1=3, 8-4=4$。最小距离是 3。
• 方案 B：选 1, 4, 9。距离分别为 $3, 5$。最小距离是 3。
• 方案 C：选 1, 8, 9。距离分别为 $7, 1$。最小距离是 1。
• 方案 D：选 2, 4, 8。距离分别为 $2, 4$。最小距离是 2。

经过尝试，最优解是方案 A 或 B，其最小间隔为 3。