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 | 無額外限制。 |