AcWing 782. 避嫌抢劫
原题链接
中等
作者:
不幸到吃土
,
2025-01-05 15:58:10
,
所有人可见
,
阅读 1
//将pair<>按坐标位置排序后,若当前a[j].y为最大值,则对于当前i及i往后位置而言,a[j].y均可作为最大值的选择对象
#include <iostream>
#include <algorithm>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
const int N = 200010;
PII a[N];
int main(){
int n,d;
cin >> n >> d;
for(int i=1;i<=n;i++){
cin >> a[i].x >> a[i].y;
}
sort(a+1,a+1+n);
int res = 0;
int maxJ = 0;
for(int i=1,j=1;i<=n;i++){ //j指向左端点,i指向右端点
while(j<i && a[i].x - a[j].x >= d){ //选出当前(j,i)区间内的最大"a[j].y"
maxJ = max(maxJ,a[j].y);
j++;
}
if(maxJ != 0){ //注意!该特判必须加:表示能找到符合条件的maxJ;若仍为0,则说明当前区间未有满足条件的(j,i)
res = max(res,a[i].y + maxJ);
}
}
cout << res << endl;
return 0;
}