C. Multi-Subject Competition

链接

[https://codeforces.com/contest/1082/problem/C]

题意

有n个人，m个科目，每个人都有选的科目si,以及他的能力值ri,

规则是每个科目要么选要么不选的，选的那些科目要求人数相同，问你最大能力总和是多少

分析

就先排序，求前缀和，后面就贪心

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
bool cmp(int a,int b){
return a>b;
}
int main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n,m;
//freopen("in.txt","r",stdin);
while(cin>>n>>m){
int r,s; vector<int> ve[N]; int sum[N];
for(int i=0;i<n;i++){
cin>>s>>r; ve[s].push_back(r);
}
int ma=0;
for(int i=1;i<=m;i++){
sort(ve[i].begin(),ve[i].end(),cmp); int len=ve[i].size(),cnt=0;
ma=max(ma,len);
for(int j=0;j<len;j++){
cnt+=ve[i][j];
if(cnt>0) sum[j+1]+=cnt;
else break;
}
}
//for(int i=0;i<ve[2].size();i++) cout<<[2][i]<<endl;
int ans=0;
for(int i=1;i<=ma;i++) ans=max(ans,sum[i]);
cout<<ans<<endl;
}
return 0;
}