Constructive Problems Never Die题解报告

先献上一位巨佬的题解 https://blog.nowcoder.net/n/216cd9c139454f498e21b266166081bb?f=comment

链接：https://ac.nowcoder.com/acm/contest/33192/C

来源：牛客网

题目描述 Grammy has a sequence A of length n.

Please find a permutation P such that
Pi ！= Ai for all i.

输入描述:

There are multiple test cases. The first line contains a single integer T(1≤T≤100000), denoting the number of test cases.

For each test case:

The first line contains a single integer nn (1≤n≤100000).

The second line contains nn integers A1,A2,…,An (1<=Ai<=n)

It is guaranteed that the sum of nn does not exceed 500000.

输出描述:

For each test case:

If the permutation does not exist, output “NO” in one line.

Otherwise output “YES” in the first line, then output n integers in the second line, denoting the permutation P1,P2,…,Pn.

示例输入

3
3
3 3 3
3
3 2 1
6
1 1 4 5 1 4

输出

NO
YES
1 3 2
YES
4 5 1 2 3 6

题目大意

具体解析

可能这个题目大意还是有一些难懂，现在，我用大白话来解释一下： 其实，就是输入一个数组，每个数a[i]的下标是i，现在，要求每个a[i]和b[i]的值都不一样（注意，是b[i]本身的值，而不是其他乱七八糟的，奇奇怪怪的东西），对于任意b[i],b[j]都可以随便交换位置，如果一种方法都没有，就输出NO，否则输出YES并把b数组打在屏幕上，值得特别注意的，是n可能达到100000，所以，某些暴力算法是会直接炸掉的（如冒泡，选择,etc.）。

献上代码

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
ll i,n,m,k,l,j;
ll a[100005],b[100005];
int main()
{
	cin>>l;
	while(l--)
	{
		ll fl=1;
		cin>>n;
		for(i=1;i<=n;i++)
		{
			cin>>a[i];
			b[i]=i;
		}
		for(i=1;i<n;i++)
		{
			if(a[i]!=a[i+1])
			{
				fl=0;
				break;
			}
		}
		if(fl)
		{
			cout<<"NO\n";
		}
		else
		{
			for(ll i=1;i<=n;i++)
			{
				if(a[i]==b[i])
				{
					for(ll j=1;j<=n;j++)
					{
						if(a[i]!=b[j]&&b[i]!=a[j])
						{
							swap(b[i],b[j]);
						}
					}
				}
			}
			cout<<"YES\n";
			for(ll i=1;i<=n;i++)cout<<b[i]<<" ";
			cout<<"\n";
		}
	}
}

（O(∩_∩)O哈哈~暴力，压着时间过，超开心！）

最后，解释一点：如果它数组中全部是相同的元素，那它自然无解，其他情况都是有解的！

$F{e}_2{O}_3+3H_{2}S{O}_4==3H_{2}O+F{e}_2(S{O}_4{)}_{3}F\; e\_2\; O\_3\; +\; 3\; H\_2\; S\; O\_4\; =\; =\; 3\; H\_2\; O\; +\; F\; e\_2\; (\; S\; O\_4\; )\_3$