cf Educational Codeforces Round 55 C. Multi-Subject Competition

admin管理员组

文章数量:1530041

原题：
C. Multi-Subject Competition
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
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≤10^ 5, 1≤m≤10^ 5) — the number of candidates and the number of subjects.

The next n lines contains two integers per line: si and ri (1≤si≤m, −10^ 4≤ri≤10^ 4) — 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
input
6 3
2 6
3 6
2 5
3 5
1 9
3 1
output
22
input
5 3
2 6
3 6
2 5
3 5
1 11
output
23
input
5 2
1 -1
1 -5
2 -1
2 -1
1 -10
output
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个学科的竞赛，这n个人每个人都只擅长一门学科，而且有一个值表示对这门学科的熟练程度（可能是负数）。现在让你选一批人去参加比赛，可以选定任何一门或几门学科参赛，但是每一门学科的参赛人数必须一样。
现在问你怎么选才能使得所有参赛人员的熟练程度的总和最大？

代码：

#include<bits/stdc++.h>

using namespace std;
const int maxn=1e5+1;

vector<vector<int>> G;
int n, m;
int mark[maxn];

int main()
{

	ios::sync_with_stdio(false);

	while(cin>>n>>m)
	{
		G.clear();
		memset(mark,-1,sizeof(mark));

		int s,r;
		for (int i=0;i<n;i++)
		{
			cin>>s>>r;
			if (mark[s] == -1) {
				mark[s] = G.size();
				G.push_back(vector<int>());
			}
			G[mark[s]].push_back(r);
		}

		int ind = 0;
		for(int i=0;i<G.size();i++)
		{
			if(!G[i].empty())
			{
				sort(G[i].begin(),G[i].end(),greater<int>());
				for(int j=1;j<G[i].size();j++)
					G[i][j] +=G[i][j-1];
			}
			ind=max(ind,int(G[i].size()));
		}
		int ans=0;
		for(int j=1;j<=ind;j++)
		{
			int tmp=0;
			for(int i=0;i<G.size();i++)
			{
				if(G[i].size()>=j &&G[i][j-1]>0)
					tmp+=G[i][j-1];
			}

			ans=max(ans,tmp);
		}

		cout<<ans<<endl;
	}
    return 0;
}

思路：

注意此题不要用普通数组来计算，即不要枚举m，会超时！

每个学科对应一批人，很容易考虑到使用hash来实现。即建立一个哈希表，key值表示学科，value值当中放置一个所有擅长此门学科学生的向量。

然后每一个学科对应的学生向量都按照学生的熟练程度从大到小排序，并计算出向量的累加值。

枚举下标值，对每一个向量按照下标横向求和得到的就是就是选定一批人数相同的人去参加竞赛时的最优解了，如果当前下标值为负值，就不要添加进求和，如果枚举的下标值大于当前向量的长度，那么就相当于当前学科的向量没有足够的人数去参赛。

例如，样例1得到

优化：

此题还可以做一下优化，首先按照参赛人数进行分层，如下图。

由上图可以知道，每一层中可以有很多行，例如第三层有3行。如果在同一层当中，第i行得到的求和值比第i-1行小或者相同，那么就可以跳过此层了，原因是因为每一个向量中的学生熟练程度都是从大到小排列的，而且存在负值，如果第i行得到的求和值比第i-1行得到的求和值还要小，那说明i+1及以后的行求和值还会更小，没有枚举的必要，直接跳到下一层去计算即可。

本文标签： codeforcesEducationalCFcompetitionSubject