题意
题目链接。
给你一个序列 $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;
}