见到有单调性、有限制的区间问题,很自然地就会想到用尺取去做。
先按工资升序排序,然后套上尺取就行了。
时间复杂度 \(O(n\log n)\)。
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int N=1e5+10;
int n,d;
struct Friend
{
int m,s;
}f[N];
bool cmp(Friend a,Friend b)
{
return a.m<b.m;
}
ll sum[N];
ll ans;
int main()
{
scanf("%d%d",&n,&d);
for(int i=1;i<=n;i++) scanf("%d%d",&f[i].m,&f[i].s);
sort(f+1,f+1+n,cmp);
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+f[i].s;
int l=1,r=1;
while(l<=n)
{
while(f[r].m-f[l].m<d&&r<=n) r++;
r--;
ans=max(ans,sum[r]-sum[l-1]);
l++;
}
printf("%lld",ans);
return 0;
}
标签:CF580B,int,题解,long,include,Friend
From: https://www.cnblogs.com/osfly/p/17774228.html