这道题比赛时候没做出来, 下来一看才发现是排序傻逼题.
把每个偏好的人做成一个 vector, 从大到小排序, 做一个前缀和. 然后将每种人数做一个桶, 在桶里装每种科目选择人数为 i 的时候分数总和.
遍历每一维 vector, 把各个位置上面的 vector 加到 sum 数组中, 最后 sum 数组里面挑出最大值.
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- vector<int> vec[100010];//vector 一定要声明类型
- ll sum[100010];
- 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++)
- {
- int subject,score;
- scanf("%d%d",&subject,&score);
- vec[subject].push_back(score);
- }
- for(int i=1;i<=m;i++)
- {
- sort(vec[i].begin(),vec[i].end(),cmp);
- }
- int maxsize=0;
- for(int i=1;i<=m;i++)
- {
- for(int j=1;j<vec[i].size();j++)
- {
- vec[i][j]+=vec[i][j-1];
- }
- maxsize=max((int)vec[i].size(),maxsize);
- }
- ll res=0;
- for(int i=1;i<=m;i++)
- {
- for(int j=0;j<vec[i].size();j++)
- {
- if(vec[i][j]>0)
- sum[j+1]+=vec[i][j];
- }
- }
- for(int i=1;i<=maxsize;i++)
- {
- //printf("%d",sum[i]);
- res=max(sum[i],res);
- }
- printf("%lld\n",res);
- }
来源: http://www.bubuko.com/infodetail-2866502.html