题目

思路:首先为NO的情况只有,某一天只可以选一个人且某人在只可以选他的情况下被选了>⌈m2⌉次。除了这种情况,其它情况不可能为NO,看一个极端的例子,总共有8天,有两个朋友1和2,有4天全是只可以选1,其它4天都是可以选1或2。那么只要让其它的天数全选2即可,2也不会超出⌈m2⌉次。

然后来看YES的情况该怎么选,首先对于只可以选一个人的天数先加在每个人的被选天数上,然后从第一天开始,遍历那一天的所有人,选出目前备选天数最低的那个人,其备选天数+1,如果遇到只有1个人可以选的直接跳过(已经预先处理了这种情况)。

Code:

#include<iostream>
#include<map>
#include<vector>
#define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const int Max = 1e6 + 5;
vector<int> vec[Max];

int main()
{
   
	FAST;
	int t;cin >> t;
	while (t--)
	{
   
		int n, m;cin >> n >> m;
		map<int, int> ma;
		int f = 0;
		for (int i = 1;i <= m;i++)vec[i].clear();
		for (int i = 1;i <= m;i++)
		{
   
			int k;cin >> k;
			for (int j = 1;j <= k;j++)
			{
   
				int a;cin >> a;
				vec[i].push_back(a);
			}
			if (k == 1)
			{
   
				ma[vec[i][0]]++;
				if (ma[vec[i][0]] > (m + 1) / 2)f = 1;
			}
		}
		if (f)cout << "NO" << endl;
		else
		{
   
			cout << "YES" << endl;
			for (int i = 1;i <= m;i++)
			{
   
				int d = 0, mi = 1e9;
				if (vec[i].size() == 1)cout << vec[i][0] << " ";
				else
				{
   
					for (int j = 0;j < vec[i].size();j++)
					{
   
						if (ma[vec[i][j]] < mi)
						{
   
							mi = ma[vec[i][j]];d = vec[i][j];
						}
					}
					cout << d << " ";
					ma[d]++;
				}
			}
			cout << endl;
		}
	}
}