2022年上海10月月赛丙组T5
发布时间
阅读量：
阅读量
2022年上海10月月赛丙组T5
组队竞赛
内存限制: 256 Mb时间限制: 1000 ms
组队竞赛
题目描述
有n同学想要参加小爱组建的一支信息学竞赛队伍，每位同学有能力值a_i,与热情度b_i,小爱认为，如果队伍当中，能力值最大与能力值最小选手之间，能力差值大于给定X，会导致能力差距过大、不利于团队的学习与凝聚力。因此，请你帮助小爱计算下，如何选择队伍的选手，才能使所有选手的能力差值小于等于X，且热情度最大。
输入格式
输入第一行，一个正整数n，表示有n位选手
接下来n行，每行两个正整数a_i,b_i,
表示每位选手的能力值与热情度。
最后一行，一个正整数X，表示小爱希望的能力差值上限
输出格式
输出一个整数，表示满足条件的情况下，最大热情度的值
数据范围
对于30%的数据，1≤n≤100
对于60%的数据，1≤n≤104
对于100%的数据，1≤n≤105,1≤d≤109,1≤a_i,b_i≤109。
样例数据
输入:
5
10 21
20 34
30 27
40 89
50 54
20
输出:
170
说明:
选第3、4、5个选手。
能力值分别为30、40、50，不超过50-30=20给定的能力差值上限20
此时热情度为27+89+54=170
思路1：
利用x枚举寻找区间，依次累加能力值并打擂台求最大值。60分。
代码1：
#include<bits/stdc++.h>
using namespace std;
int main(){
long long a[200010],b[200010],x,n,ans=0;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
}
cin>>x;
for(int i=1;i<=n;i++){
long long s=0;
for(int j=1;j<=n;j++){
if(a[j]>=a[i]&&a[j]-a[i]<=x)
s=s+b[j];
}
ans=max(ans,s);
}
cout<<ans<<endl;
return 0;
}
思路2：
sort排序，利用能力值枚举。
全部评论 (0)
还没有任何评论哟~