CF580B Kefa and Company

前言。

其实本题与这道题极为相似，所以建议降橙。

思路

因为输入顺序不影响就结果，所以可以先给 \(a\) 按照工资从小到打排序一下序（这里 \(a\) 使用 MAP）。然后再使用尺取法，只要 \(a_{r+1}\) 的值减 \(a_l\) 的值 \(\lt k\) 就将 \(r\) 加 \(1\)。然后发现每次都暴力统计友谊值会超时，所以可以用前缀和：\(sum_i\) 用来记录前 \(i\) 个数的和。

AC 代码

#include<bit/stdc++.h>
using namespace std
#define N 100005
long long t,mx,n,k,x,sum[N];
struct node{
	long long num,val;
}a[N];
void two_pointer(){
    for(long long l=1,r=0;l<=n;l++){
        while(r<n&&a[r+1].num-a[l].num<k){
        	r++;
		}
		mx=max(mx,sum[r]-sum[l-1]);
    }
    return;
}
bool cmp(node a,node b){
	return a.num<b.num;
}
void read(){
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i].num>>a[i].val;	
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i].val;
}
void init(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
}
int mian(){
	init();
	read();
	two_pointer();
	cout<<mx<<endl;	
}

珍爱生命，请勿抄袭（抄抄试试？）。

AC 记录