充电站选址

题目背景

一条笔直的公路连接着 $n$ 个村庄，第 $i$ 个村庄位于公路上的位置 $a_i$。为了更好地服务村民，小 R 计划在公路沿途修建若干充电站。由于每座充电站的供电距离有限，小 R 希望合理选址，让每个村庄都能用上最近充电站的电。

题目描述

给定 $n$ 个村庄在公路上的位置 $a_1, a_2, \dots, a_n$（可能有重复位置），以及要修建的充电站数量 $k$。

充电站可以建在公路上的任意位置（包括村庄所在位置）。一个村庄与充电站的距离等于两者位置之差的绝对值。小 R 希望每个村庄到最近充电站的距离都不超过 $D$，求满足条件的最小整数 $D$。

输入格式

第一行两个整数 $n, k$。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$。

输出格式

一行一个整数，表示满足条件的最小整数 $D$。

样例输入 1

5 2
1 3 7 9 15

样例输出 1

3

样例解释 1

当 $D = 3$ 时，可以把第一个充电站建在位置 $4$（覆盖村庄 $1, 3, 7$），第二个充电站建在位置 $12$（覆盖村庄 $9, 15$），所有村庄都满足条件；可以验证 $D = 2$ 时至少需要 3 个充电站。因此答案为 $3$。

样例输入 2

4 1
2 8 20 30

样例输出 2

14

样例解释 2

只有一个充电站，建在位置 $16$ 时，距离最远的村庄 $2$ 和 $30$ 到它的距离都是 $14$；当 $D = 13$ 时村庄 $30$ 无法被覆盖。因此答案为 $14$。

数据范围

对于 100% 的数据，$1 \le k \le n \le 2 \times 10^5$，$1 \le a_i \le 10^9$。

特殊性质：

• A：村庄位置等距分布。
• B：$k = n$。
• C：$k = 1$。

样例 1 满足测试点 1,2 的约束条件；样例 2 满足测试点 1,2 的约束条件。

数据包

以下大样例随题下发（Data.zip），用于本地自测，与评测数据不同：

下载 Data.zip