首先观察题目,发现题目要求 \(x\) 个一模一样的数
因为这 \(x\) 个数是定下来的,所以从这里突破
假设已经选择了 \(x\) 个数,还剩下 \(n-x\) 个数,我们的目标是从中取出 \(y-x\) 个数,然后让这些数在这 \(n-x\) 个位置里面移动,直到这 \(y-x\) 个数不与原序列上的数一样,然后剩下的 \(n-y\) 个数用这个序列里没有出现的那个数填上即可
首先判断是否有解
我们将剩下的这 \(n-x\) 个数按照个数排序,让出现次数更多的一种数排在后面,如果两种数出现次数相同,则按编号排序
举个例子,样例:
5 2 4
3 1 1 2 5
假设我们选了前两个数作为 \(x\) 个数,那么还剩下
1 2 5
其中 \(1\) 、\(2\) 、\(3\) 的个数都是1(都只出现了一次)
如果我们选择第一个数和第四个数作为 \(x\) 个数,那么还剩下
1 1 5
排序之后变为(分别出现了两次和一次)
5 1 1
换个普遍的,抽象的图
假设这是已经排好序了的数组,颜色表示不同数字,长方形的长度代表这种数字的出现次数
我们将其按照这种方式进行重排序:
即将最后一种数字放到最前面,剩下的数字之间的相对顺序不变,然后依次放在后面
注意,现在表示的意义:与原来的长方形相比,所相对的数字的位置该放的数
我知道说了听不懂,所以举个例子
假设原数组
1 2 2 3 3 3
排序后:
3 3 3 1 2 2
代表的意思就是原来放1的位置(第一个位置)现在放3;原来两个放2的位置(第二个位置和第三个位置)现在放了两个三;原来放3的位置(第四五六个位置)现在放了一个1(第四个位置)和两个2(第五六个位置),一 一对应
如果此时最长的一个长方形的长度没有超过总长度的一半,很显然就是一个可行解
如果超过了一半,比如下图
由于我们还有 \(n-y\) 个位置可以填充,那么就会变成下面这个样子
如果这 \(n-y\) 个位置让最长的长方形的长度在减小后不在超过总长度的一半,那么此时也是一个解
如果再加上了这 \(n-y\) 个位置之后最长的长方形的长度都还超过了一半,那么就肯定无解了
请认真思考为什么这种放置和重新排序一定是最优的(即不可能存在另一种方式使得在我们这种策略无解的情况下有解)
那么我们只需要限制每个长方形的长度取数即可
有许多细节,建议好好写代码
下面给出参考代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
int n;
int a[N];
int pot[N],tot[N],cnt[N],ans[N];
int num;
vector<int> pos[N];
bool vis[N],mark[N];
void init()
{
num=0;
for(int i=1;i<=n+1;i++) vis[i]=mark[i]=cnt[i]=tot[i]=pot[i]=0;
for(int i=1;i<=n+1;i++) pos[i].clear();
}
int read()
{
int x=0,f=1;char s=getchar();
while(s<'0'||s>'9')
{
if(s=='-') f=-f;
s=getchar();
}
while(s>='0'&&s<='9')
{
x=x*10+s-48;
s=getchar();
}
return x*f;
}
bool cmp(int i,int j)
{
if(tot[a[i]]==tot[a[j]]) return a[i]<a[j];
return tot[a[i]]<tot[a[j]];
}
int main()
{
int t=read();
while(t--)
{
n=read();
int x=read(),y=read();
for(int i=1;i<=n;i++)
{
a[i]=read();
vis[a[i]]=1;
pos[a[i]].push_back(i);
cnt[a[i]]++;
}
int temp=n-x;
for(int i=1;i<=n+1;i++)
if(vis[i])
{
if(temp>min((n+n-y-x>>1),cnt[i]))
{
temp-=min((n+n-y-x>>1),cnt[i]);
tot[i]=min((n+n-y-x>>1),cnt[i]);
}
else
{
tot[i]=temp;
temp=0;
break;
}
}
if(temp)
{
printf("NO\n");
init();
continue;
}
for(int i=1;i<=n+1;i++)
for(int j=1;j<=tot[i];j++)
pot[++num]=pos[i][j-1];
sort(pot+1,pot+num+1,cmp);
for(int i=num,j=num-tot[a[pot[num]]];j;i--,j--)
ans[pot[i]]=a[pot[j]],mark[pot[i]]=1;
for(int j=1;j<=tot[a[pot[num]]];j++)
ans[pot[j]]=a[pot[num]],mark[pot[j]]=1;
for(int i=1;i<=n+1;i++)
if(!vis[i])
{
temp=i;
break;
}
if(tot[a[pot[num]]]>n-y)
for(int i=tot[a[pot[num]]]-n+y+1;i-(tot[a[pot[num]]]-n+y+1)<n-y;i++)
ans[pot[i]]=temp;
else
for(int i=1;i<=n-y;i++)
ans[pot[i]]=temp;
for(int i=1;i<=n;i++)
if(!mark[i])
{
x--;
ans[i]=a[i];
mark[i]=1;
if(!x) break;
}
printf("YES\n");
for(int i=1;i<=n;i++) printf("%d ",ans[i]);
puts("");
init();
}
return 0;
}