今日学习记录
1. 2528. 最大化城市的最小电量
关键词：贪心 二分答案 差分
问题分析：
核心思路:
二分答案
最小的最大值,不用想就是二分答案
差分
我们要预处理得到每个城市的电量,要使用范围的修改,使用差分技巧实现
贪心
check 函数是二分的第二个难点,这个题就是看电站怎么放,我们可以从头开始遍历之前处理好的城市电量数组 arr,我们考虑当左端点小于 ans 的时候,就示意该右边一定是要放一个电站的,对于每一个左端点,我们优先考虑满足左端点
tip:此题不是答案递增的,小心二分的写法,要使用开区间的写法,
**最终代码：
typedef long long ll;
class Solution {
public:
long long maxPower(vector<int>& stations, int r, int k) {
int n = stations.size();
vector<ll> arr(n+1,0);
for(int i = 0;i<n;i++){
int x = stations[i];
int l = i-r>=0?i-r:0,rt = i+r+1<=n?i+r+1:n;
arr[l] += x,arr[rt] -= x;
}
ll mn = arr[0],mx = arr[0];
for(int i = 1;i<n;i++){
arr[i] = arr[i-1]+arr[i];
mn = min(arr[i],mn);
mx = max(arr[i],mx);
}
auto check = [&](ll mid)->bool{
vector<ll> dif(n+1);
ll sum = 0,cnt = 0;
for(int i = 0;i<n;i++){
sum += dif[i];
ll m = mid-(arr[i]+sum);
if(m<=0) continue;
cnt += m;
if(cnt>k) return false;
sum += m;
dif[min(n,i+2*r+1)] -= m;
}
return true;
};
ll left = mn,right = mx+k+1;
ll ans = mn;
while(left<right){
ll mid = left+(right-left)/2;
if(check(mid)) left = mid+1,ans = mid;
else right = mid-1;
}
return ans;
}
};学到的点：
- 二分写法
- 差分