AcWing 782. 避嫌抢劫
原题链接
中等
作者:
Value
,
2020-04-27 11:43:13
,
所有人可见
,
阅读 617
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2 * 100010;
typedef pair<int, int> pii;
pii a[N];
int main(){
int n, dis;
cin >> n >> dis;
for(int i = 0; i < n; i ++ ) scanf("%d%d", &a[i].first, &a[i].second);
sort(a, a+n);
int i, j;
i = j = 0;
while(i < n && a[i].first - a[j].first < dis) i ++ ; //找到一个符合条件的银行
if(i == n) cout << "0" << endl;
else{ //从0 到 i 银行开始枚举
int bestFit = a[0].second; //定义最佳的j的位置打劫收益
int res = bestFit; //答案
while(i < n){ //枚举i银行
//在0 - i之间寻找j的最佳打劫收益, j肯定不会超过i,故可以不加j < i的条件
while(a[i].first - a[j].first >= dis){
bestFit = max(bestFit, a[j].second);
j ++ ;
}
res = max(res, bestFit + a[i].second); //更新答案
i ++ ;
}
cout << res << endl;
}
return 0;
}