范围求值
获得某一范围的最大值
非固定长度(满足一定约束)
摘水果
人固定在startPos,移动距离是k。范围就是 2*x + y <= k, 先朝某一方向走x步,然后再朝另一方向走到startPos后走y步。
可以便利所有的[l,r]的情况,然后二分查找位置,利用前缀和相加。
但是这条约束还可以进一步化简为 r - l + min(r - startPos, startPos - l) <= k
所以可以先找到最右边的l,然后往右走一步:
- 满足约束,相加
- 不满足约束,左边前进一步
一些琐碎的细节:
- 不满足约束时,
l最多前进到startPos右边第一个。此时计算距离需要加abs - 使用
tmp来保存这一”滑动窗口”的值 - 不满足条件时,
l前进一步,r需要固定住1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28class Solution {
public:
int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) {
int n = fruits.size();
int l = 0;
while(l < n && fruits[l][0] + k < startPos) l++;
int ans = 0;
int r = l;
for(;r < n && fruits[r][0] <= startPos;r++)
ans += fruits[r][1];
int left_wall = r;
int tmp = ans;
for(;r < n && l <= left_wall;r++){
int cost = fruits[r][0] - fruits[l][0] +
min(fruits[r][0] - startPos,abs(startPos - fruits[l][0])) ;
if(cost <= k){
tmp += fruits[r][1];
ans = max(ans,tmp);
}else{
tmp = tmp - fruits[l][1];
r--;
l++;
}
}
return ans;
}
};