P15237 [NHSPC 2025] 邮局

在一条直线道路上共有 $n$ 个小镇，第 $i$ 个小镇的坐标为 $x_i$；两个小镇之间的距离定义为其坐标差的绝对值。 现计划在 $k$ 个小镇设置邮局，设置邮局后，可能会有一些邮局暂停营业，目标是让所有小镇到最近的营业邮局距离尽可能短。 具体而言，对于第 $i$ 个小镇的居民，他们的「安全容忍范围」是一个整数 $s_i$，不论哪 $s_i$ 家邮局暂停营业，他们仍希望能就近前往某一营业中的邮局。设在有至多 $s_i$ 家邮局暂停营业的最差情况下，离这个小镇最近的邮局距离为 $d_i$。我们的目标是最小化所有小镇中 $d_i$ 的最大值。

$$ \begin{aligned} & n\ k \\ & x_1\ s_1\ \dots \ x_n\ s_n \end{aligned} $$ * $n$ 代表小镇的数量。 * $k$ 代表要建设的邮局数量。 * $x_i$ 和 $s_i$ 分别代表第 $i$ 个小镇的坐标和安全容忍范围。

$$a$$ * $a$ 代表在最佳方式建设下，$\max_{1 \leq i \leq n} d_i$ 的最小值。

### 数据限制 * $2 \le n \le 10^6$。 * $1 \le k \le n$。 * $0 \le s_i < k$。 * $1 \le x_i \le 10^9$。 * 输入的数皆为整数。 ### 评分说明 本题共有五组子任务，条件限制如下所示。 每一组可有一或多笔测试资料，该组所有测试资料皆需答对才会获得该组分数。 | 子任务 | 分数 | 额外输入限制 | | :------: | :----: | ------------ | | 1 | 4 | $n \le 1000$，$k = 1$。 | | 2 | 19 | $n \le 1000$。 | | 3 | 17 | $n \le 10^5$，$x_i \le 10^6$，$s_i = 0$。 | | 4 | 33 | $n \le 10^5$，$x_i \le 10^6$。 | | 5 | 27 | 无额外限制。 |