给你一个下标从 0 开始长度为
n的整数数组stations，其中stations[i]表示第i座城市的供电站数目。每个供电站可以在一定 范围 内给所有城市提供电力。换句话说，如果给定的范围是
r，在城市i处的供电站可以给所有满足|i - j| <= r且0 <= i, j <= n - 1的城市j供电。
|x|表示x的 绝对值 。比方说，|7 - 5| = 2，|3 - 10| = 7。一座城市的 电量 是所有能给它供电的供电站数目。
政府批准了可以额外建造
k座供电站，你需要决定这些供电站分别应该建在哪里，这些供电站与已经存在的供电站有相同的供电范围。给你两个整数
r和k，如果以最优策略建造额外的发电站，返回所有城市中，最小电量的最大值是多少。这
k座供电站可以建在多个城市。示例 1：
输入：stations = [1,2,4,5,0], r = 1, k = 2 输出：5 解释： 最优方案之一是把 2 座供电站都建在城市 1 。 每座城市的供电站数目分别为 [1,4,4,5,0] 。 - 城市 0 的供电站数目为 1 + 4 = 5 。 - 城市 1 的供电站数目为 1 + 4 + 4 = 9 。 - 城市 2 的供电站数目为 4 + 4 + 5 = 13 。 - 城市 3 的供电站数目为 5 + 4 = 9 。 - 城市 4 的供电站数目为 5 + 0 = 5 。 供电站数目最少是 5 。 无法得到更优解，所以我们返回 5 。示例 2：
输入：stations = [4,4,4,4], r = 0, k = 3 输出：4 解释： 无论如何安排，总有一座城市的供电站数目是 4 ，所以最优解是 4 。提示：
n == stations.length1 <= n <= 1050 <= stations[i] <= 1050 <= r <= n - 10 <= k <= 109
差分数组+二分答案+贪心
注意到答案具有单调性，即值越大，越能/不能满足要求；值越小，越不能/能满足要求。所以二分答案。
check答案的逻辑为 判断用k次建站机会能否达到指定的最小电力值，这里考虑贪心的去建站，即从左向右遍历站点，如果当前站点 i 需要新的电力以达到目标电力值，则在 i+r的地方建x个电力站，x为目标电力值-当前站点电力值。建站后区间[i,i+2*r] 内所有的站点都增加了x点电力，这是个区间修改操作，于是考虑用差分数组（支持O(1)区间修改）。注意及时还原当前站点的差分数组，以获取当前站点电力值。（不用担心还原了差分数组而导致区间修改失效，因为还原的部分是在当前站点的左侧部分，而需要区间修改的部分总是在右侧，不影响，所以可以做到一边还原一边差分的“神奇”操作）。
class Solution {
public:
long long maxPower(vector<int>& stations, int r, int k) {
vector<long long>arr(stations.size() + 2, 0);
for(int i=0;i<stations.size();i++){
int left=max(0,i-r);
int right=min(i+r,static_cast<int>(stations.size()));
arr[left]+=stations[i];
arr[right + 1]-=stations[i];
}
long long left=0,right= (long long)(k)+100000ll*stations.size();
long long ans = 0;
while(left<=right){
long long mid=(left+right)/2; // 二分答案 ，假设mid是最终答案，即最小电力的最大值
if(k>=calNeed(arr,stations.size(),r,mid)){
// k是题目允许的最大建站数量,如果够用，还可以继续放大二分的答案，即收缩二分的左端点。
left=mid+1;
ans=mid;
}else{
right=mid-1;
}
}
return ans;
}
// 计算在指定最小电力值为now时，所需的建站数量
long long calNeed(vector<long long> arr,int stationSize,int r,long long now) {
long long need = 0;
for(int i=0;i<stationSize;i++) {
if(i>0)arr[i]+=arr[i-1]; // 还原差分数组
if(arr[i]<now) {
// 贪心：如果当前位置缺电力，则选择在 i+r的位置建站是最“经济实惠的”
long long count =now-arr[i]; // 建站的数量
// 差分数组的区间修改操作，整个区间都加上count
arr[i]+= count;
arr[min(i+2*r+1,stationSize)]-=count;
need+=count;
}
}
return need;
}
};
