朴素的就是枚举0 ~ 1e6 将往后2k内的草全部加起来 显然复杂度行不通
根据上述思路 稍作优化 我们可以考虑枚举每片草作为左端点 用二分查找右端点( r <= l + 2 * k)
因为要用到二分 要排序使数列有序 然后再用前缀和来计算区间和
代码如下
再提一嘴 因为区间长度固定 用长度为2 * k的滑动窗口遍历一遍也是可以的
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
int main()
{
int n, k;
cin >> n >> k;
vector<int> d(n), pre(n + 1);
vector<PII> q(n);
for(int i = 0; i < n; i++) cin >> q[i].second >> q[i].first;
//以坐标排序小到大
sort(q.begin(), q.end());
int res = 0;
for(int i = 0; i < n; i++) d[i] = q[i].first, pre[i + 1] = pre[i] + q[i].second;
for(int i = 0; i < n; i++)//枚举每一片草
{
int l = d[i];//坐标
int r = upper_bound(d.begin(), d.end(), l + 2 * k) - d.begin();
res = max(res, pre[r] - pre[i]);
}
cout << res << endl;
return 0;
}