GitBook

这里写图片描述

以钱数进行排序 对每个可同时参加的区间的总友好度进行统计 每次遇见新的人判断是否能与最左端的人同在 不能的话则把最左端的人删掉 以此改变sum值 并更新max

#include<stdio.h>
#include<algorithm>
using namespace std;
struct node {
	int m,s;
} a[100200];
bool cmp(node A,node B) {
	return A.m<B.m;
}
int main() {
	int n,d;
	while(scanf("%d %d",&n,&d)!=EOF) {
		for(int i=0; i<n; i++) {
			scanf("%d %d",&a[i].m,&a[i].s);
		}
		sort(a,a+n,cmp);
		int l=0;
		__int64 max=0,sum=0;
		for(int i=0; i<n; i++) {
			sum+=(__int64)a[i].s;
			while(a[i].m>=a[l].m+d) {
				sum-=(__int64)a[l].s;
				l++;
			}
			if(max<sum)
				max=sum;
		}
		printf("%I64d\n",max);
	}
	return 0;
}

题目地址: 【CodeForces】[580B]Kefa and Company