AcWing 782. 避嫌抢劫
原题链接
中等
作者:
跟着灿哥学切菜
,
2021-02-08 01:12:10
,
所有人可见
,
阅读 390
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 200020;
int n, d;
PII banks[N];
int main() {
cin >> n >> d;
for (int i = 1; i <= n; i ++) cin >> banks[i].first >> banks[i].second;
sort(banks + 1, banks + 1 + n);
int res = 0;
for (int i = 1, j = 0, maxV = -1e9; i <= n; i ++) {
//如果此时j可以往后移动一个位置
while (j + 1 < i && banks[i].first - banks[j + 1].first >= d) {
j ++;
maxV = max(maxV, banks[j].second);
}
res = max(res, banks[i].second + maxV);
}
cout << res << endl;
return 0;
}