政府批准了可以额外建造 k 座供电站，你需要决定这些供电站分别应该建在哪里，这些供电站与已经存在的供电站有相同的供电范围。
给你两个整数 r 和 k ，如果以最优策略建造额外的发电站，返回所有城市中，最小供电站数目的最大值是多少。
一. 二分法+前缀和+贪心
分析：最大化最小值，首先考虑使用二分法，逐步试探满足条件的上界值
从左往右遍历，贪心地使得左边城市的先满足条件
同时贪心将电站建到最远处，计算此时需要的供电站数，同时更新其他位置的值（使用临时数据）
这里要预先计算出各个城市实际所拥有的电站数，通过前缀和的方式，发电范围内做差即可（注意边界处理）
每次新生成临时数组更新超时
class Solution {
public:
long long maxPower(vector<int>& stations, int r, int k) {
//最大化供电站的数目
int n = stations.size();
vector<long> presum(n+1);
vector<long> power(n);
for(int i=0;i<n;i++)
presum[i+1] = presum[i] +stations[i];
for (int i = 0; i < n; i++)
power[i] = presum[min(i + r + 1, n)] - presum[max(i - r, 0)]; // 电量
long left = *min_element(power.begin(),power.end());
long right = *max_element(power.begin(),power.end())+k;
while(left<right){
vector<long> cur = power;//每次循环重置
long need = 0;
long mid = (left+right+1)/2;//目标是让所有供电站都大于等于mid
for(int i=0;i<n;i++){//从左往右贪心建电站，不用考虑左侧，建在最远处
long m = mid - cur[i];//差值
if(m>0){//需要m个电站
need+=m;//建到最远处，同时给其他地方供电
for(int j=i;j<min(n,2*r+i+1);j++)
cur[j] = cur[j]+m;
}
}
if(need>k) right = mid-1;
else left = mid ;//最大化
}
return left;
}
};
二. 差分数组优化
class Solution {
public:
long long maxPower(vector<int>& stations, int r, int k) {
//最大化供电站的数目
int n = stations.size();
vector<long> presum(n+1);
vector<long> power(n);
for(int i=0;i<n;i++)
presum[i+1] = presum[i] +stations[i];
for (int i = 0; i < n; i++)
power[i] = presum[min(i + r + 1, n)] - presum[max(i - r, 0)]; // 电量
long left = *min_element(power.begin(),power.end());
long right = *max_element(power.begin(),power.end())+k;
while(left<right){
vector<long> dif(n);//差分数组初始化
long sum_dif = 0;
long need = 0;//用于与给定值做判断
long mid = (left+right+1)/2;//目标是让所有供电站都大于等于mid
for(int i=0;i<n;i++){//从左往右贪心建电站，不用考虑左侧，建在最远处
sum_dif+=dif[i];//累加差分值，辅助后面的更新
long m = mid - (power[i]+sum_dif);//差值
if(m>0){//需要m个电站
need+=m;//建到最远处，同时给其他地方供电
if(need>k){right =mid-1;break;}//剪枝
sum_dif+=m;//后面范围内的电站的同样进行更新
if(i+2*r+1<n) dif[i+2*r+1]-=m;//这个值只作用这该范围，后面要剪掉
}
}
if(need>k) right = mid-1;
else left = mid ;//最大化
}
return left;
}
};