2022CCPC威海 A. Dunai （gym104023A）

Problem - A - Codeforces

题目大意：现给出前n届TI（dota2国际邀请赛）的冠军队伍名单，他们分别负责1到5号位，然后给出m个下一届TI的候选选手名单，组队的规则是五个人必须每人承担1-5号位，且必须至少有一人拿过冠军，问最多能组成多少队伍

1<=n<=100;1<=m<=1000

思路：因为要求每支队伍中至少有一个冠军，所以我们可以从冠军入手，给冠军匹配队友，所以我们先挑出在候选名单里的冠军，然后统计每个位置上的人数，从人数最少的那个位置的冠军开始选，使其他位置上的人数减去当前位置冠军的人数，如果减到0了就说明有一个位置空了，只要一个位置空了，就组不成任何队伍了，结束统计

#include<iostream>
#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
int cntch[10];
pair<int, int>cnt[10];
bool cmp(pair<int,int> a, pair<int,int> b)
{
	return a.second < b.second;
}
int main()
{
	map<string, int>ch;
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= 5; j++)
		{
			string temp;
			cin >> temp;
			ch[temp] = j;//储存冠军的名字
		}
	}
	int m;
	for (int i = 1; i <= 5; i++)
	{
		cnt[i].first = i;//初始化每个位置的编号
	}
	cin >> m;
	for (int i = 1; i <= m; i++)
	{
		string temp;
		int pos;
		cin >> temp;
		scanf("%d", &pos);
		if (ch.find(temp) != ch.end())
		{//如果当前候选选手是冠军
			cntch[pos]++;//记录这个位置上有多少冠军
		}
		cnt[pos].second++;//记录每个位置有多少候选选手
	}
	sort(cnt + 1, cnt + 6,cmp);//将每个位置的人数按从小到大排序
	int ans = 0;
	bool flag = 1;
	for (int i = 1; i <= 5; i++)
	{
		int pos = cnt[i].first;
		for (int j = 1; j <= 5; j++)
		{
			if(cnt[j].second>=cntch[pos])//冠军人数不变而当前位置的人数会变少，所以需要先判断能不能选完
				cnt[j].second -= cntch[pos];
			else
			{
				cntch[pos] = cnt[j].second;//维护答案更新的值
				cnt[j].second = 0;
			}
			if (cnt[j].second == 0)
				flag = 0;//有一个位置没选手了，就没法组更多队伍了
		}
		ans += cntch[pos];
		cntch[pos] = 0;//当前位置冠军置为0
		if (!flag)
			break;
	}
	cout << ans;
}