题目内容

$CDN$(content delivery network，内容分发网络)机房可以加速网站内容的加载速度，通过在地理位置上靠近用户的地点存储网站的内容副本。

给定一个下标从 $0$ 开始长度为 $n$ 的整数数组 $cities$ ，其中 $cities$ 表示第 $i$ 座 城市中现有的 $CDN$ 机房数量。

每个 $CDN$ 机房能够服务的城市覆盖范围由其所在位置决定，所有节点具有相同的城市盖范围。

如果给定的覆盖范围是 $r$ ，则位于城市 $i$ 的 $CDN$ 机房可以为其周围 $∣i-j∣<=r$ 范围内的所有城市提供服务，这里 $∣x∣$ 表示 $x$ 的绝对值。例如，$∣5-3∣=2，∣4-9∣=5$ 。

题解思路

对于长度为 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，则判定不可行。