CF1530D Secret Santa 题解

Problem

Solution

每个人初始不会给自己送礼物。

如果每人要送礼的人都不一样，答案即为 \(n\)。

如果有两个或以上的人要送给同一个人礼物，假设有 \(x\) 个人要给同一个人送礼物，那么必有 \(x-1\) 个人要更改送礼的人，并将礼物送个 \(x-1\) 个没有礼物收的人。然而这样送礼物可能会导致有人送礼物给自己，对于这种情况，我们不妨让这个人就送礼给自己本来要送的人，而这样的操作也不会影响不改变送礼的人的数量。

于是我们定义一个 \(t_i\) 表示最后一个要给 \(i\) 送礼的人，再定义 \(in_i\) 表示要给 \(i\) 送礼的人数，先统计没人给其送礼的人，再处理有人要给其送礼的人，分两种情况：

1. 只有一人要给其送礼，该位置不改变；

2. 有多人要给其送礼，满足最后一人（这里是满足最后一人，也可以满足别人），即 \(t_i\)，同时 \(in\) 数组减一。

最后扫一遍判断是否有要送给自己的人并处理即可。

Code

#include<bits/stdc++.h>
using namespace std;
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define FOR(i,a,b) for(int i=(a);i>=(b);i--)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define elif else if

const int N=2e5+4;
int n,a[N],in[N],t[N],same[N],sum,ans[N];
void solve()
{
	cin>>n;
	For(i,1,n)in[i]=t[i]=0;
	For(i,1,n)cin>>a[i],in[a[i]]++,t[a[i]]=i;
	same[0]=0;
	For(i,1,n)if(in[i]==0)same[++same[0]]=i;
	sum=0;
	For(i,1,n)
		if(in[a[i]]==1)ans[i]=a[i],sum++;
		elif(in[a[i]]!=0)
		{
			ans[i]=same[same[0]--];
			in[a[i]]--;
		}
	For(i,1,n)
		if(ans[i]==i)
		{
			ans[i]=a[i];
			ans[t[a[i]]]=i;
			t[a[i]]=i;
		}
	cout<<sum<<"\n";
	For(i,1,n)cout<<ans[i]<<" ";
	cout<<"\n";
}
int main()
{
	IOS;
	int T;cin>>T;
	while(T--)solve();

	return 0;
}