Codeforces Contest 1082 C Multi-Subject Competition——枚举

admin管理员组

文章数量:1530016

A multi-subject competition is coming! The competition has m different subjects participants can choose from. That’s why Alex (the coach) should form a competition delegation among his students.

He has n candidates. For the i-th person he knows subject si the candidate specializes in and ri — a skill level in his specialization (this level can be negative!).

The rules of the competition require each delegation to choose some subset of subjects they will participate in. The only restriction is that the number of students from the team participating in each of the chosen subjects should be the same.

Alex decided that each candidate would participate only in the subject he specializes in. Now Alex wonders whom he has to choose to maximize the total sum of skill levels of all delegates, or just skip the competition this year if every valid non-empty delegation has negative sum.

(Of course, Alex doesn’t have any spare money so each delegate he chooses must participate in the competition).

Input
The first line contains two integers n and m (1≤n≤105, 1≤m≤105) — the number of candidates and the number of subjects.

The next n lines contains two integers per line: si and ri (1≤si≤m, −104≤ri≤104) — the subject of specialization and the skill level of the i-th candidate.

Output
Print the single integer — the maximum total sum of skills of delegates who form a valid delegation (according to rules above) or 0 if every valid non-empty delegation has negative sum.

Examples
inputCopy
6 3
2 6
3 6
2 5
3 5
1 9
3 1
outputCopy
22
inputCopy
5 3
2 6
3 6
2 5
3 5
1 11
outputCopy
23
inputCopy
5 2
1 -1
1 -5
2 -1
2 -1
1 -10
outputCopy
0
Note
In the first example it’s optimal to choose candidates 1, 2, 3, 4, so two of them specialize in the 2-nd subject and other two in the 3-rd. The total sum is 6+6+5+5=22.

In the second example it’s optimal to choose candidates 1, 2 and 5. One person in each subject and the total sum is 6+6+11=23.

In the third example it’s impossible to obtain a non-negative sum.

题意：

给你n个人，m种学科，每个人都有擅长的学科s，在这个学科种他能拿到r的分数，让你制定一个计划，参加那些学科并且参加的学科安排的人数相等，并且收益最大，可以不选择所有学科，可以不让所有人去。

题解：

先排个序，使得人数的分布是这样的：

并且在每一列（列就是科目，行就是人）内也是从大到小排序，之后再每一列算一个前缀和，并且在前缀和到这个列的最底端或者到0结束，这很容易证得：小于0的时候不如不取。之后就是for行数，就是第一列的人数，在每一行for一遍现有的列数，看起来这是n*n，其实是n.

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct node
{
    int sum;
    vector<int>vec;
    bool operator< (const node& a)const
    {
        return sum>a.sum;
    }
}e[N];
int cmp(int x,int y)
{
    return x>y;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int x,y;
    for(int i=1;i<=n;i++)
        scanf("%d%d",&x,&y),e[x].vec.push_back(y),e[x].sum++;
    sort(e+1,e+m+1);
    int all=m,ans=0;
    for(int i=1;i<=m;i++)
    {
        if(e[i].sum==0)
        {
            all=i-1;
            break;
        }
        sort(e[i].vec.begin(),e[i].vec.end(),cmp);
        if(e[i].vec[0]<=0)
        {
            e[i].sum=0;
            continue;
        }
        for(int j=1;j<e[i].sum;j++)
        {
            e[i].vec[j]+=e[i].vec[j-1];
            if(e[i].vec[j]<=0)
            {
                e[i].sum=j;
                break;
            }
        }
    }
    sort(e+1,e+1+all);
    for(int i=1;i<=all;i++)
        if(e[i].sum==0)
        {
            all=i-1;
            break;
        }
    for(int i=1;i<=e[1].sum;i++)
    {
        while(e[all].sum<i)
            all--;
        int sum=0;
        for(int j=1;j<=all;j++)
            sum+=e[j].vec[i-1];
        ans=max(ans,sum);
    }
    printf("%d\n",ans);
    return 0;
}

本文标签： ContestcodeforcescompetitionSubjectMulti