CF1530D Secret Santa

题目意思

对一个长度为 n 的序列 a，可以对其任意一个数进行变化，求在让序列所有数中位置 i 的数不能是 i，并且序列中有 1 到 n 之间的所有数。

思路

我们建一个 b 数组存每个数出现的次数。如果他是 0，说明这个数需要其他数变化得到。然后往后枚举每一个数，如果当前被枚举的数有两个或以上，且不和当前位置相等，说明可以更换，更换一下就好了，最后输出。

#include<bits/stdc++.h> using namespace std; const int N=200005; int T,n,a[N],b[N]; int main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>T; while(T--){ cin>>n; for(int i=1;i<=n;i++){ b[i]=0; } for(int i=1;i<=n;i++){ cin>>a[i]; b[a[i]]++; } int id=1,ans=0; for(int i=n;i>=1;i--){ if(!b[i]){ ans++; while(b[a[id]]<2||i==id) id++; b[a[id]]--,a[id]=i; } } cout<<n-ans<<"\n"; for(int i=1;i<=n;i++) cout<<a[i]<<' '; cout<<"\n"; } return 0; }