题意

题目链接。

给你一个序列 $a$，让你输出一个序列 $b$ ，这个 $b$ 满足跟 $a$ 有 $x$ 个位置上的元素一样。有 $y$ 个元素跟 $a$ 里边的元素一样。值域是 $1\le v \le n+1$。

解析

先考虑这么一件事情：假如你已经确定了这 $x$ 个位置是什么，那么问题转化为：你需要将若干个元素交换位置，使得与原来元素相同的位置不超过 $n-y$ 个（由于值域为 $[1,n+1]$，一定存在一个合法的且没有在 $a$ 中出现过的元素）。

对于这个问题，我们可以将相同的元素相邻排列，例如得到一个序列 $[1,1,1,2,2,2,3,3,4]$，我们记其中最长的相同元素长度为 $l$（例如在上述序列中，$l=3$），然后将所有元素向右平移 $l$ 个单位。

然后我们发现，答案不合法当且仅当 $l$ 大于序列长度的一半。换言之，我们需要使最长的相同元素最短，这样我们对于选定的 $x$ 个位置，只需要一直选择当前最多的那种元素即可，这可以通过优先队列实现。

对于剩下的元素，我们可以在排列元素时按从多至少排列（上述例子序列就符合这一点），这样的话最终若不合法，不合法元素一定出现在序列的最前面，因此我们只需要强令序列的前 $n-y$ 个元素为那个未出现过的元素，其余位置依照平移法则即可。若仍然不符合要求，则输出 NO。

代码

#include<bits/stdc++.h>
#define pi pair<int,int>
#define fi first
#define se second
#define mk make_pair
using namespace std;
const int N=1e5+5;
int T,n,x,y,a[N],ans[N],K;
pi b[N];
struct node{
    int cnt;
    queue<int> q;
}c[N];
priority_queue<pi> q;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&n,&x,&y);
        while(!q.empty()) q.pop();
        for(int i=1;i<=n+1;i++){
            c[i].cnt=0;
            while(!c[i].q.empty()) c[i].q.pop();
        }
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            c[a[i]].cnt++;c[a[i]].q.push(i);
        }
        for(int i=1;i<=n+1;i++){
            q.push(mk(c[i].cnt,i));
            if(!c[i].cnt) K=i;
        }//将每个元素放在一起，并找出未出现的元素
        for(int i=1;i<=x;i++){
            pi t=q.top();
            int u=t.se;q.pop();
            ans[c[u].q.front()]=u;
            c[u].q.pop();
            if(t.fi!=1) q.push(mk(t.fi-1,t.se));
        }//优先选择最多的 x 个元素
        int now=1,l=q.top().fi;
        while(!q.empty()){
            pi t=q.top();q.pop();
            int u=t.se;
            while(!c[u].q.empty()){
                b[now]=mk(u,c[u].q.front());
                c[u].q.pop();now++;
            }
        }//其他元素重新排列
        for(int i=1;i<=n-y;i++){
            ans[b[i].se]=K;
        }//强行处理前 n-y 个
        for(int i=n-y+1;i<=n-x;i++){
            int pos=i-l;if(pos<=0) pos+=n-x;
            ans[b[i].se]=b[pos].fi;
        }//其余的遵循平移法则
        int cnt=0;
        for(int i=1;i<=n;i++) if(ans[i]==a[i]){cnt++;}
        if(cnt>x){printf("NO\n");}
        else{
            printf("YES\n");
            for(int i=1;i<=n;i++) printf("%d ",ans[i]);
            printf("\n");
        }
    }
    return 0;
}