建设银行积分兑换网站,江夏区做网站,免费在线制作图片,三雷网站程序力扣2528.最大化城市的最小电量
题目解析及思路
题目要求找到所有城市电量最小值的最大
电量为给城市供电的发电站数量
因此每座城市的电量可以用一段区间和表示#xff0c;即前缀和 二分最低电量时 如果当前城市电量不够,贪心的想发电站建立的位置#xff0c;应该是在mi…力扣2528.最大化城市的最小电量
题目解析及思路
题目要求找到所有城市电量最小值的最大
电量为给城市供电的发电站数量
因此每座城市的电量可以用一段区间和表示即前缀和 二分最低电量时 如果当前城市电量不够,贪心的想发电站建立的位置应该是在min(ir,n−1)因为左侧城市电量足够了 建立发电站可以用差分优化
代码
class Solution {
public:long long maxPower(vectorint stations, int r, int k) {int n stations.size();long sum[n1],power[n],dif[n];sum[0] 0;//前缀和for(int i0;in;i)sum[i1] sum[i] stations[i];//预处理每座城市的电量for(int i0;in;i)power[i] sum[min(ir1,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 i0;in;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[i2*r1] - 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;}
};
