题目思路
从交换相邻这里，我们可以明显看出来，这有些类似冒泡排序。
但是，我们要来思考一下怎样情况输出 NO。
我们就用冒泡排序的代码来分析一下。为了方便分析，就用 for 循环版的。
for(int i=1;i<=n-1;i++)
{
for(int j=1;j<=n-i;j++)
{
if(a[j]<a[j+1])
{
swap(a[j],a[j+1]);
}
}
}我们能很快的反应出来，$(n-1)\times (n-i)$ 肯定是比 $n^2$ 要小的。
所以，$n^2$ 的操作绰绰有余。
因此，我们只要判断数组元素是否相同就可以了，不用考虑能否在 $n^2$ 次操作内完成。
我们先写出判断一样的代码。
int n=read();
int a[n+1],b[n+1],c[n+1],d[n+1];
for(int i=1;i<=n;i++)
{
cin>>a[i];
c[i]=a[i];
}
for(int i=1;i<=n;i++)
{
cin>>b[i];
d[i]=b[i];
}
sort(c+1,c+n+1);
sort(d+1,d+n+1);
//因为不能打乱ab数组，就用别的数组代替。如果排序后一模一样，里面元素也一样。
for(int i=1;i<=n;i++)
{
if(c[i]!=d[i]){puts("NO");return;}//判断ab数组元素是否相同
}接着，如果可以构造出来，我们就可以每次确定一个数的位置，最后就能创造出来。
puts("YES");
for(int i=1;i<=n;i++)//循环b的元素
{
int x;
for(int j=i;j<=n;j++)
{
if(a[j]==b[i])
{
x=j;//找位置
break;
}
}
for(int j=x;j>i;j--)//交换
{
swap(a[j],a[j-1]);
cout<<j<<" "<<j-1<<'\n';
}
}
cout<<0<<" "<<0<<'\n';完整代码
完整代码戳这
#include<bits/stdc++.h>
using namespace std;
int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
void solve()
{
int n=read();
int a[n+1],b[n+1],c[n+1],d[n+1];
for(int i=1;i<=n;i++)
{
cin>>a[i];
c[i]=a[i];
}
for(int i=1;i<=n;i++)
{
cin>>b[i];
d[i]=b[i];
}
sort(c+1,c+n+1);
sort(d+1,d+n+1);
for(int i=1;i<=n;i++)
{
if(c[i]!=d[i]){puts("NO");return;}
}
puts("YES");
for(int i=1;i<=n;i++)
{
int x;
for(int j=i;j<=n;j++)//这里赛时写错过了，事后被同学 hack 了 QwQ
{
if(a[j]==b[i])
{
x=j;
break;
}
}
for(int j=x;j>i;j--)
{
swap(a[j],a[j-1]);
cout<<j<<" "<<j-1<<'\n';
}
}
cout<<0<<" "<<0<<'\n';
}
int main()
{
int t=read();
while(t--)
{
solve();
}
return 0;
}