P8197 [传智杯 #4 决赛] 排排队

cyq 在 tsyz 担任了体育老师，负责排队一事。

在 tsyz 中，每个人都有一个身高 ai​，并且只有相邻的两个人可以交换位置。cyq 带领的队伍有 n 个人,他现在要给大家排队形。

给定一个长度为 n 的序列 b，一个队形被认为美观，当且仅当对于所有的 i=1,2,3,…n，ai​=bi​。cyq 想知道，他能否让大家的队形变得美观，并且交换相邻两个人的次数不超过 n^2 次。这个问题把 cyqcyq 难住了，请你帮他来解决这个问题，如果存在合法的交换方案，输出 YES，并给出一组方案；否则，输出 NO。

输入格式

本题单测试点内有多组测试数据。

第一行是一个整数 T，表示数据组数，对于每组数据：
第一行是一个整数，表示队伍的长度 n。
第二行有 n 个整数，第 i 个整数表示第 i 个人的身高 ai​。
第三行有 n 个整数，第 i 个整数表示美观队形里第 i 个人的身高 bi​。

输出格式

对每组数据依次分别输出答案。

对于每组数据，若存在一种方案，则在第一行输出一个 YES，否则输出一个 NO。

如果输出 YES，下面则输出若干行每行两个整数 i,j，表示第 i个同学和第 j个同学交换位置，显然 ∣i−j∣=1。在交换完成后，你还需要输出一行  0 表示你的操作结束了，请注意数组的下标从 1 开始编号至 n。

如果输出 NO，则接下来什么都不需要输出。

请特别注意，对于每组数据，你的操作次数不能超过 n^2（不包括 0 0 一行），否则将得到 WA(Wrong Answer) 的结果。

输入输出样例

输入 #1复制

3
4
1 2 2 3
3 2 2 1
3
1 2 3
1 2 4
1
1
1

输出 #1复制

YES
4 3
2 3
1 2
3 2
3 4
0 0
NO
YES
0 0

说明/提示

数据规模与约定

对于全部的测试点，保证 1≤T≤10，1≤n≤103，1≤ai​,bi​≤109，且各个测试点 n 之和不超过 1000，即 ∑n≤103。

提示

• 请注意大量的输出输出对程序效率造成的影响，不要频繁刷新缓冲区。例如，对于使用 std::cout 的 C++ 选手，请使用 '\n' 而不是 std::endl 来换行；对于 java 选手，请选择高效率的输出方式，如使用 PrintWriter；python 选手可以正常的使用 print 而无需考虑效率问题。
• 请按照输出格式的要求输出您的答案，如果格式不符合要求，返回的评测信息将可能是 TLE、RE、WA、UKE 等任何结果。

C++ 语言的高效输出样例

#include <iostream>
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  for (int i = 1; i <= 5; ++i) {
    std::cout << i << '\n'; // 注意这里不能使用 std::endl
  }
}

Java 语言的高效输出样例

import java.io.PrintWriter;
 
public class Main {
  public static void main(String[] args) {
    PrintWriter ot = new PrintWriter(System.out);
    for (int i = 1; i <= 5; ++i) {
      ot.println(i);
    }
    ot.flush(); // 请务必保证在程序结束时运行本条语句，否则在缓冲区的内容无法输出
  }
}

#include <iostream>
#include <algorithm>
using namespace std;
 
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n,a[1005],a1[1005],b[1005],b1[1005],temp=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            a1[i]=a[i];
        }
        for(int i=1;i<=n;i++){
            scanf("%d",&b[i]);
            b1[i]=b[i];
        }
        sort(a1+1,a1+n+1);
        sort(b1+1,b1+n+1);
        for(int i=1;i<=n;i++){
            if(a1[i]!=b1[i])
                temp=1;
        }
        if(temp){
            printf("NO\n");
        }
        else{
            printf("YES\n");
            for(int i=1;i<=n;i++)//循环b的元素
            {
                int x;
                for(int j=1;j<=n;j++)
                {
                    if(a[j]==b[i])
                    {
                        x=j;
                        break;
                    }
                }
                for(int j=x;j>i;j--)
                {
                    swap(a[j],a[j-1]);
                    printf("%d %d\n",j,j-1);
                }
            }
            printf("0 0\n");
        }
    }
}