题解思路

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

题目内容

$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<=10^9$

输出描述

返回所有城市中最小服务质量达到最大时的 $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$ 。