C. Basic Diplomacy （思维、贪心）

谁践踏了优雅 2021-07-16 23:17 397阅读 0赞

[题目][Link 1]

思路：首先为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;
    		}
    	}
    }

[Link 1]: https://codeforc.es/contest/1484/problem/C