题解思路
对于长度为 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，则判定不可行。
P3715.第2题-最大化城市CDN节点建设的最小服务质量
题目内容
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 。
一座城市的“服务质量”定义为能够访问到的 CDN 机房的数量，你的任务是在全国范围内选择多个城市来新建 k 个 CDN 机房(同一个城市可重复建设)，以确保即使在网络流量高峰时期也能提供最佳的服务质量。
现在给定两个整数 r 和 k ，你需要决定在哪些城市新建 k 个 CDN 机房，使所有城市中最小的服务质量达到最大，并返回最小服务质量。
输入描述
第一行数字为 r ，第二行数字为 k ，第三行数字为城市数量 n ，第四行 n 个数字为 cities 的值
输入限制：
1<=n<=100000
0<=cities[i]<=100000
0<=r<=n−1
0<=k<=109
输出描述
返回所有城市中最小服务质量达到最大时的 CDN 节点数
样例1
输入
1
2
5
1 2 4 9 3
输出
5
说明
输入转换成 cities=[1,2,4,9,3]，r=1，k=2
最优方案之一是把 2 个节点都建在城市 1 ，建设完后每座城市的CDN节点数目分别为 [1,4,4,9,3] 。
-
城市 0 的节点数目为 1+4=5。
-
城市 1 的节点数目为 1+4+4=9 。
-
城市 2 的节点数目为 4+4+9=17 。
-
城市 3 的节点数目为 4+9+3=16 。
-
城市 4 的节点数目为 9+3=12 。
这些城市中节点数最小的是 5 ，已无法使得这个最小值更大。
样例2
输入
0
3
4
5 5 5 5
输出
5
说明
输入转换成 cities=[5,5,5,5]，r=0，k=3。无论如何安排，总有一座城市的 CDN 节点数目是 5 ，所以最优解是 5 。
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
