范围求值

获得某一范围的最大值

非固定长度(满足一定约束)

摘水果
人固定在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
    28
    class 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;
    }
    };