【Educational Codeforces Round 55 (Rated for Div. 2) C. Multi-Subject Competition】 排序+贪心

C. Multi-Subject Competition

题意

给你n个数字，每个数字属于一个组，对于每个组，可以选择选或者不选，最终选择一些组，每个组选出一些数字，要求每组选的数字个数相等，而且所有数字的和最大。
$1<=n<=10^5$
做法

对每组的数字sort，暴力枚举选1个，选2个…选maxx（数字最多的组的数字个数）个，

代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
int s[maxn],r[maxn];
vector<vector<int> > v;
vector<int> tmp[maxn];
vector<ll> sum[maxn];
bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){
    scanf("%d%d",&s[i],&r[i]);tmp[s[i]].push_back(r[i]);}for(int i=1;i<=m;i++){
    if(tmp[i].size()!=0) v.push_back(tmp[i]);}int maxx=0;for(int i=0;i<v.size();i++){
    maxx=max(maxx,(int)v[i].size());sort(v[i].begin(),v[i].end(),cmp);int sz=v[i].size();ll tmp=0;for(int j=0;j<sz;j++){
    if(j==0) tmp=v[i][j];else tmp=tmp+v[i][j];sum[i].push_back(tmp);}}ll ans=0;for(int i=1;i<=maxx;i++){
    ll tt=0;for(int j=0;j<v.size();j++){
    if(v[j].size()>=i&&sum[j][i-1]>=0) tt+=sum[j][i-1];}ans=max(ans,tt);}printf("%lld\n",ans);return 0;
}