题解思路

对于长度为 n 的城市数组 cities，每座城市初始拥有若干 CDN 机房。每个机房的服务半径为 r，相当于它能为相距不超过 r 的城市提供服务。给定还可以新建 k 个机房，允许在同一城市重复建设，目标是使所有城市的最小“服务质量”（即能访问到的机房总数）最大化。

我们可以抽象为：让每个城市 i “窗口”内（[i–r, i+r]）的机房总和至少达到 m，问是否能用不超过 k 次增量操作做到这一点。增量操作：在某个城市 j 新增一台机房，会使得所有覆盖到 j 的城市窗口内总和加 1。

• 二分答案：对最小服务质量 m 进行二分搜索。
• 可行性检验：固定候选值 m，判断是否在 k 次新增内使所有城市窗口和 ≥ m。
• 贪心策略：从城市 0 到 n–1 遍历，维护当前对每个城市由新增机房带来的累计增量 cur_add（通过差分数组模拟区间加法）。若某城市窗口和 initial[i] + cur_add 小于 m，则在最右能覆盖该城市的点 j = min(n–1, i+r) 上新增所需的机房数 need = m – (initial[i] + cur_add)，并将 need 加到差分数组上。若累计新增量超出 k，则判定不可行。