AcWing 782. 避嫌抢劫
原题链接
中等
作者:
偷月亮的喵
,
2024-11-09 10:21:11
,
所有人可见
,
阅读 1
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n ,d;
const int N = 1e6+ 10;
typedef pair<int, int> PII;
#define x first
#define y second
PII a[N];
int res;
int main(){
cin >> n >> d;
for (int i = 1; i <= n; i ++ ){
cin >> a[i].x >> a[i].y;
}
sort(a + 1, a + n + 1);int mx = -1e9;//必须让 mx+a[i].y<=0,所以mx直接初始化很小的数
for (int i = 1, j = 0; i <= n; i ++){
while (j + 1 < i && a[i].x - a[j+1].x >= d){
mx = max(mx, a[++j].y);
}
res = max(res, mx + a[i].y);
}
cout << res << '\n';
return 0;
}