1506E Restoring the Permutation (优先队列)

不念不忘少年蓝@ 2021-07-16 22:10 259阅读 0赞

[题目][Link 1]

思路：首先可以肯定的是，在某个数第一次出现时，在那个位置一定要填该数，因为它更新了那个最大的数，这些数的位置是固定的。  
对于求最小的情况，只需从1–n开始填那些不是固定的数空出来的地方,如果该数是上文提到的固定的数则跳过。  
对于求最大的情况，创建一个multiset（当作一个优先队列来使用,按降序排列），从开始的位置1遍历到n,如果遇到一个固定的数则输出该数，然后将该数之前到上一个固定数之间的数insert进multiset。如果该位置不是固定的数，则将multiset中最大的数输出，然后erase掉该数。这样做的原因是，要想数列最大，又不能超过前面那个数，如果超过了就会造成更新，而更新的固定的数已经确定，所以每次遇到一个新的最大数就将其和上一个最大数之间的数压进优先队列，每次输出队列中的最大数。

Code:

#include<iostream>
    #include<map>
    #include<set>
    using namespace std;
    const int Max = 1e6 + 5;
    int lst[Max], ls[Max];
    
    int main()
    { 
    	int t;cin >> t;
    	while (t--)
    	{ 
    		int n;cin >> n;
    		multiset<int,greater<int>> set;
    		map<int, int> ma;
    		for (int i = 1;i <= n;i++)
    		{ 
    			int a;cin >> a;
    			lst[i] = a;
    			ma[a]++;
    		}
    		for (int i = 1;i <= n;i++)
    		{ 
    			if (lst[i] == lst[i - 1])ls[i] = 0;
    			else ls[i] = lst[i];
    		}
    		int g = 1;
    		for (int i = 1;i <= n;i++)
    		{ 
    			if (ls[i])cout << ls[i] << " ";
    			else
    			{ 
    				while (ma[g] != 0) g++;
    				cout << g++ << " ";
    			}
    		}
    		cout << endl;
    		int l=0;
    		for (int i = 1;i <= n;i++)
    		{ 
    			if (ls[i])
    			{ 
    				for (int j = l+1;j <= ls[i]-1;j++) set.insert(j);
    				cout << ls[i] << " ";
    				l = ls[i];
    			}
    			else
    			{ 
    				cout << *set.begin() << " ";
    				set.erase(set.begin());
    			}
    		}
    		cout << endl;
    	}
    }

[Link 1]: https://codeforc.es/contest/1506/problem/E