先献上一位巨佬的题解 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哈哈~暴力，压着时间过，超开心！）
最后，解释一点：如果它数组中全部是相同的元素，那它自然无解，其他情况都是有解的！
京公网安备 11010502036488号