P8197
一扶苏一
·
·
题解
C. 排排队
题意：给定两个长度为 n 的序列 a, b，每次操作只能交换 a 中相邻两个数，求能否在 n^2 次操作内使 a, b 相同，如果可以则构造方案。
**关键词**：构造，选择排序，冒泡排序。
**参考难度**：橙/黄。
**分析**：考虑如果存在一个数 $x$，满足 $x$ 在 $a, b$ 内的出现次数不同，则显然无解。换句话说，如果 $a, b$ 都从小到大排序以后不同，则无解，因此可以先用另一个数组对二者排序，判掉这种情况。
考虑判掉无解以后的情况构造有解的方法：使用类似选择排序的方法，从 1 到 $n$ 枚举 $i$，若 $a_i \neq b_i$，则在 $i$ 后面找到一个 $j$ 满足 $a_j =b_i$，然后交换 $(j, j -1), (j - 1, j - 2), \dots (i + 1, i)$，这样就可以把 $j$ 交换到 $i$。
对于每个 $b_i$ 找到对应的 $j$ 是一个类似选择排序的过程，因此这一步是单次 $O(n)$ 的；将 $j$ 交换到 $i$ 是一个类似冒泡排序的过程，对于每个 $i$，交换的过程也是 $O(n)$。注意这两部分是相互独立的，因此时间复杂度是相加而不是相乘。枚举 $i$ 还有 $O(n)$ 的复杂度，因此总的复杂度是 $O(n^2)$。
考虑交换的次数：显然对于一个 $i$，其交换次数不会超过 $n$，因此总的交换次数不超过 $n^2$。更精细的分析可以发现交换次数的上界是 $\frac{n(n - 1)}{2}$。因为交换是一个类似冒泡排序的过程，因此也可以套用冒泡排序的理论，得到总交换次数不超过 $n^2$ 的结论。
(C++)
```cpp
#include <array>
#include <iostream>
#include <algorithm>
const int maxn = 1005;
std::array<int, maxn> a, b, c, d;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int T, n;
for (std::cin >> T; T; --T) {
std::cin >> n;
a.fill(0); b.fill(0);
for (int i = 1; i <= n; ++i) std::cin >> a[i];
for (int i = 1; i <= n; ++i) std::cin >> b[i];
c = a; d = b;
std::sort(c.begin(), c.end());
std::sort(d.begin(), d.end());
if (c != d) {
std::cout << "NO\n";
} else {
std::cout << "YES\n";
for (int i = 1; i <= n; ++i) if (a[i] != b[i]) {
for (int j = i; j <= n; ++j) if (a[j] == b[i]) {
for (int k = j; k > i; --k) {
std::swap(a[k], a[k - 1]);
std::cout << k << ' ' << k - 1 << '\n';
}
break;
}
}
std::cout << "0 0\n";
}
}
}
```
(java)
```java
import java.util.Scanner;
import java.util.Arrays;
import java.io.PrintWriter;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
PrintWriter out = new PrintWriter(System.out);
for (int T = cin.nextInt(); T != 0; --T) {
int n = cin.nextInt();
int[] a = new int[n], b = new int[n], c = new int[n], d = new int[n];
for (int i = 0; i < n; ++i) {
c[i] = a[i] = cin.nextInt();
}
for (int i = 0; i < n; ++i) {
d[i] = b[i] = cin.nextInt();
}
Arrays.sort(c);
Arrays.sort(d);
boolean flag = true;
for (int i = 0; i < n; ++i) if (c[i] != d[i]) {
flag = false; break;
}
if (flag == false) {
out.println("NO");
} else {
out.println("YES");
for (int i = 0; i < n; ++i) if (a[i] != b[i]) {
for (int j = i + 1; j < n; ++j) if (a[j] == b[i]) {
for (int k = j; k > i; --k) {
out.println((k + 1)+ " " + k);
int t = a[k]; a[k] = a[k - 1]; a[k - 1] = t;
}
break;
}
}
out.println(0 + " " + 0);
}
}
out.flush();
}
}
```
(Python)
```python
T = int(input())
for t in range(T):
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c, d = list(), list()
for i in a:
c.append(i)
for i in b:
d.append(i)
c.sort()
d.sort()
if c != d:
print("NO")
else:
print('YES')
for i in range(0, n):
if a[i] != b[i]:
for j in range(i, n):
if (a[j] == b[i]):
k = j
while (k != i):
print(k, k + 1)
a[k], a[k - 1] = a[k - 1], a[k]
k -= 1
break
print(0, 0)
```