CF#842-div2-C

题意

给定一个序列 A ，让你构造两个序列 B C 满足：
\(max(B[i],C[i])=A[i]\)
能构造输出YES然后输出两个构造序列BC，不能构造输出NO

题解

显然，我想到如果A序列中出现三个及以上的相同的一个数，必错。因为两个序列使某下标位置保持最大值最多只能出现两次。
既然已知NO的情况，下面来想如何构造。
我想的是分“无重复”和“有重复”两种情况讨论，其实可以归纳为一种情况。
即枚举A，未重复出现过放到B中，重复出现过的放到C中，此时已经构造出了部分序列。
剩下的位置，采用未填入的值用可以填入的最大值的策略填充。

具体说明未填入的值用可以填入的最大值

首先通过pair<int,int>记录好空的位置另一个序列填入的值以及当前下标；
然后根据sort对pair中的first排序，排好备用；
通过visa[],visb[]数组记录当前序列中有哪些值；
然后根据priority_queue优先队列存遍历vis后不存在(要填的)那些值；
然后根据贪心策略，对每一个序列，先从大到小遍历需要填入的下标，然后把优先队列中的值填进去，因为需要填的一定是允许填入当前位置的，和最开始构造序列时填的最大值相关，所以一定能满足填入要求，完毕。
题外话，向pair中添加使用语句make_pair(,)。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=2e5+100;
int a[N];
int cnt[N];
int p[N],q[N];
pii aa[N],bb[N];
int visa[N],visb[N];
bool cmp(int a,int b){
    return a>b;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            visa[i]=0;
            visb[i]=0;
            cnt[i]=0;
        }
        vector<int> ve;
        int f=1;
        for(int i=1;i<=n;i++){
            cnt[a[i]]++;
            ve.push_back(a[i]);
            if(cnt[a[i]]>2){
                f=0;
                break;
            }
        }
        sort(ve.begin(),ve.end(),cmp);
        int now=n;
        for(int i=0;i<ve.size();i++){
            if(ve[i]>=now){
                now--;
            }else{
                f=0;
                break;
            }
        }
        if(!f){
            cout<<"NO\n";
        }else{
            cout<<"YES\n";
            vector<int> vp;
            int ida=0,idb=0;
            for(int i=1;i<=n;i++){
                if(cnt[a[i]]==1){
                    p[i]=a[i];
                    visa[a[i]]=1;
                    bb[++idb]=make_pair(a[i],i);
                    q[i]=0;
                }else{
                    p[i]=0;
                    visb[a[i]]=1;
                    q[i]=a[i];
                    aa[++ida]=make_pair(a[i],i);
                    vp.push_back(a[i]);
                    cnt[a[i]]--;
                }
            }
            if(!vp.size()){
                for(int i=1;i<=n;i++){
                    if(q[i]==0) q[i]=p[i];
                }
            }else{
				//未填
                sort(aa+1,aa+1+ida);
                sort(bb+1,bb+1+idb);
                priority_queue<int> qa,qb;
                for(int i=1;i<=n;i++){
                    if(!visa[i]){
                        qa.push(i);
                    }
                    if(!visb[i]){
                        qb.push(i);
                    }
                }
                for(int i=ida;i>=1;i--){
                    p[aa[i].second]=qa.top();
                    qa.pop();
                }
                for(int i=idb;i>=1;i--){
                    q[bb[i].second]=qb.top();
                    qb.pop();
                }
            }
            for(int i=1;i<=n;i++){
                cout<<p[i]<<" ";
            }
            cout<<"\n";
            for(int i=1;i<=n;i++){
                cout<<q[i]<<" ";
            }
            cout<<"\n";
        }
    }
	return 0;
}