题解 | #Constructive Problems Never Die#

题目描述

就是输出的数组里面$p_{i}p\_i$ !=$a_{i}a\_i$

解析

因为区间需要用1~n的数字来填，所以这里我们直接开一个1~n的数组再去填上给的坑。 我们可以直接用数组填上坑，这里大家可能有疑问，直接放不会影响到后面的结果吗？回答是：肯定的。所以我们 当判到后面无法存放的时候，我们可以与前面交换（直接swap），前提是当前位置与交换位置均可放下 交换值与当前值。然后复杂度的话也是合格的，因为最差情况就是我们从1开始扫到n，只有第n个能放 这时候你可能会觉得复杂度很大，但是当i继续循环下去的时候，a[i]==b[i]剪了点小枝，继续循环下去 大家伙自己看吧。

献上代码

#include<bits/stdc++.h>
using namespace std;
int t;
int n;
int a[100003];
int b[100003];
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			b[i]=i;
		}
		bool f=1;
		for(int i=1;i<=n;i++){
			if(a[i]==b[i]){
				f=0;
				for(int j=1;j<=n;j++){
					if(i!=j&&a[i]!=b[j]&&b[i]!=a[j]){//判断交换条件
						swap(b[i],b[j]);
						f=1;
					}
				}
			}
			if(f==0) break;
		}
		if(f==0) cout<<"NO\n";
		else {
			cout<<"YES\n";
			for(int i=1;i<=n;i++){
				printf("%d ",b[i]);
            }
		    cout<<"\n";
		}
	}
}