原题链接

做到一道接雨水的题,感觉和这道有点相似,都是边走边记录最值

我的思路：

一开始是想从前后两面开始遍历,但是这样后面的指针仍然需要回溯,与O(n^2)的暴力法没什么差别,因此此思路错误

正解思路:

对银行的距离进行排序,如果i位置与j位置相差d,那么i+1位置与j的距离至少有d,当i前进的时候,j就不需要回溯 ,时间复杂度最大O(2*n)

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
struct bank{
    int d,money;
    bool operator<(bank s){
        return this->d<s.d;
    }
}bank[N];
int main()
{
    int n,d,maxn = -1000,maxj = -1000;//猜想之前的错误原因是maxn和maxj开得不够小 
    scanf("%d%d",&n,&d);
    for(int i=1;i<=n;i++) scanf("%d%d",&bank[i].d,&bank[i].money);
    sort(bank+1,bank+n+1); 
    for(int i=1,j=1;i<=n;++i){
        while(j<i&&bank[i].d>=bank[j].d+d){//优化方案,在j前进的时候记录最大值,这样避免回溯 
            maxj = max(maxj,bank[j].money);
            ++j;
        }
        maxn = max(maxj+bank[i].money,maxn);
    }
    printf("%d\n",maxn);
}