3597: 最优信号塔

在一个长度为 $n$ 的笔直公路上，有 $n$ 个村庄，编号从 1 到 $n$，第 $i$ 个村庄的位置是 $a_i$（位置不重复，且已按升序给出）。

政府计划建设 恰好 $k$ 座信号塔，每座信号塔可以建在任意一个村庄的位置上。

信号塔的覆盖范围是 半径 $r$：如果一座信号塔建在位置 $x$，它可以覆盖所有满足 $\mathrm{\mid }p-x\mathrm{\mid }\le r$ 的村庄 $p$。

目标是：选择 $k$ 个村庄建塔，使得所有村庄都被覆盖，并且最小化覆盖半径 $r$。

请你求出：最小可能的 $r$。

注意：你需要同时决定塔的位置和半径

$\mathrm{r<span\; style="font-family:KaTeX\_Math;font-size:1.21em;font-style:italic;">r</span><span\; style="font-family:-apple-system,\; blinkmacsystemfont,\; "font-size:12px;letter-spacing:0.064px;text-wrap-mode:wrap;background-color:\#FFFFFF;">，但\; </span>}$$k$

给定 $n$ 个村庄位置和 $k$，求最小的覆盖半径 $r$，使得用 $k$ 座塔能覆盖所有村庄。

• 第一行：两个整数 $n$ 和 $k$（$1\le k\le n\le {10}^5$）
• 第二行：$n$ 个整数 $a_1,a_2,\dots ,a_n$，表示村庄位置（$1\le a_i\le {10}^9$，升序）

• 一行一个整数：最小的覆盖半径 $r$

7 2
1 3 5 7 10 13 15

3