力扣2528.最大化城市的最小电量

力扣2528.最大化城市的最小电量

题目解析及思路

题目要求找到所有城市电量最小值的最大

电量为给城市供电的发电站数量

因此每座城市的电量可以用一段区间和表示，即前缀和

• 二分最低电量时

  • 如果当前城市电量不够,贪心的想发电站建立的位置，应该是在min(i+r,n−1)，因为左侧城市电量足够了

  • 建立发电站可以用差分优化

代码

class Solution {
public:long long maxPower(vector<int>& stations, int r, int k) {int n = stations.size();long sum[n+1],power[n],dif[n];sum[0] = 0;//前缀和for(int i=0;i<n;i++)sum[i+1] = sum[i] + stations[i];//预处理每座城市的电量for(int i=0;i<n;i++)power[i] = sum[min(i+r+1,n)] - sum[max(i-r,0)];auto check = [&](long min_power) -> bool{//差分数组只用来存变化量memset(dif,0,sizeof(dif));long sum_d = 0,need = 0;for(int i=0;i<n;i++){sum_d += dif[i];//最低 - 初始 - 新建立 = 仍需long m = min_power - power[i] - sum_d;if(m > 0){//need用于判断结果need += m;if(need > k) return false;//差分的左端点sum_d += m;if(i + 2*r +1 < n) dif[i+2*r+1] -= m; }}return true;};long left = *min_element(power, power + n), right = left + k; // 开区间写法while (left < right) {long mid = (left + right + 1)/ 2;check(mid) ? left = mid: right = mid - 1;}return left;}
};