leetcode5955.摘水果（困难，周赛）

自己没思路，感觉下标处理太麻烦了。。。
有两种情况：
1.假设人向左走 y 步，然后回到原点，再向右走 x步。
2.假设人向右走 y 步，然后回到原点，再向左走 x步。
写法：枚举x的长度即为所有情况！！！

for (int x = 0; x <= k; ++x)  {
	int y = (k - x) / 2;
	[startPos - x, startPos + y]的区间和（向右走 y 步，然后回到原点，再向左走 x步）
	[startPos - y, startPos + x]的区间和（向左走 y 步，然后回到原点，再向右走 x步）
}

方法一：二分查找下标（用稀疏区间和处理）

class Solution {
public:
    int maxTotalFruits(vector>& fruits, int startPos, int k) {
        
        vector sum, pos;
        sum.push_back(0);
        for (auto& each : fruits) {
            sum.push_back(sum.back() + each[1]);
            pos.push_back(each[0]);
        }
        int it1, it2;
        int ans = INT_MIN;
        for (int x = 0; x <= k; ++x) {
            int y = (k - x) / 2; //向下取整，才能保证向右走x步
            //[startPos - x, startPos + y]区间和
            it1 = lower_bound(pos.begin(), pos.end(), startPos - x) - pos.begin();
            it2 = upper_bound(pos.begin(), pos.end(), startPos + y) - 1 - pos.begin();
            ans = max(ans, sum[it2 + 1] - sum[it1]);

            //[startPos - y, startPos + x]
            it1 = lower_bound(pos.begin(), pos.end(), startPos - y) - pos.begin(); 
            //lower_bound()函数大于pos最大值返回pos.end()
            it2 = upper_bound(pos.begin(), pos.end(), startPos + x) - 1 - pos.begin();
            ans = max(ans, sum[it2 + 1] - sum[it1]);
        }
        return ans;
    }
};

方法二：计算出取值范围内所有的区间和

class Solution {
public:
    int maxTotalFruits(vector>& fruits, int startPos, int k) {
        
        vector sum(200005);
        for (auto& each : fruits) {
            sum[each[0]] = each[1];
        }
        for (int i = 1; i < 200005; ++i) {
            sum[i] = sum[i - 1] + sum[i];
        }
        int ans = INT_MIN;
        for (int x = 0; x <= k; ++x) {
            int y = (k - x) / 2;
            int ma = (startPos + y > 200004) ? sum[200004] : sum[startPos + y]; //右端点可能会越界
            int mi = (startPos - x == 0 || startPos - x < 0) ? 0 : sum[startPos - x - 1]; //左端点可能会越界
            ans = max(ans, ma - mi);
           
            ma = (startPos + x > 200004) ? sum[200004] : sum[startPos + x];
            mi = (startPos - y == 0 || startPos - y < 0) ? 0 : sum[startPos - y - 1];
            ans = max(ans, ma - mi);
        }
        return ans;
    }
};

易错点：
1：右端点可能会越界。。。
2：左端点可能会越界。。。