1481C Fence Painting (list、map)

偏执的太偏执、 2021-07-16 14:09 338阅读 0赞

[题目][Link 1]

思路：  
对于失败有两种情况：  
1.统计所有的需要修正成各种颜色的数目，如果发现对于一种颜色我们所拥有的画师数少于所需修正的数目，则失败。  
2.我们会发现其实可能有画师会画不属于b\[i\]中所有的颜色，如果这个画师是最后一位画师（最后画）那么没有任何的画师可以在之后将他的画修改为正确颜色，失败。

再来分析成功的画师分配：对于每个需要修改颜色的地方用队列做位置记录，分配画师的时候队列不空就pop掉一个,空了的话就（也就是这种画师该修改的颜色位置已经全部修正完毕，该画师多余）直接修改最后一个画师的画，反正最后一个画师会将其修正为正确颜色，还要小心分析一下最后一个画师的位置，如果最后一个画师所画颜色所需数量和画师数量一样，那这个最后一个画师所画位置=队列中此颜色最后一个push的，如果最后一个画师是剩余的那么找到一个匹配其颜色的位置即可。

#include<iostream>
    #include<memory.h>
    #include<queue>
    #include<map>
    using namespace std;
    typedef long long ll;
    const int Max = 1e5 + 5;
    int h[Max], b[Max];
    int lst[Max], ls[Max];
    queue<int> q[Max];
    
    int main()
    { 
    	int t;cin >> t;
    	while (t--)
    	{ 
    		int n, m;cin >> n >> m;
    		map<int, int> mag, mah, ma;
    		for (int i = 1;i <= n;i++) {  cin >> lst[i];ma[lst[i]]++; }
    		for (int i = 1;i <= n;i++) {  cin >> ls[i];ma[ls[i]]++; }
    		for (int i = 1;i <= m;i++) {  cin >> h[i];mah[h[i]]++;ma[h[i]]++; }
    		for (auto i = ma.begin();i != ma.end();i++)q[i->first] = queue<int>();
    		for (int i = 1;i <= n;i++)
    		{ 
    			if (lst[i] != ls[i])
    			{ 
    				q[ls[i]].push(i);
    				mag[ls[i]]++;
    			}
    		}
    		int f = 0, last = 0;
    		for (auto i = mag.begin();i != mag.end();i++)
    		{ 
    			if (mah[i->first] < i->second) {  f = 1;break; }
    		}
    		for (int i = 1;i <= n;i++)if (ls[i] == h[m])last = i;
    		if (mah[h[m]] == mag[h[m]])last = q[h[m]].back();
    		if (last == 0)f = 1;
    		if (f)cout << "NO" << endl;
    		else
    		{ 
    			cout << "YES" << endl;
    			for (int i = 1;i <= m;i++)
    			{ 
    				if (!q[h[i]].empty())
    				{ 
    					cout << q[h[i]].front()<<" ";q[h[i]].pop();
    				}
    				else cout << last<<" ";
    			}
    			cout << endl;
    		}
    	}
    }

[Link 1]: https://codeforc.es/problemset/problem/1481/C