自动搬运

查看原文

来自洛谷，原作者为

	一扶苏一 休息结束。邮箱 yifusuyi@qq.com

搬运于2025-08-24 22:36:51，当前版本为作者最后更新于2022-03-12 20:23:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

C. 排排队

题意：给定两个长度为 $n$ 的序列 $a, b$，每次操作只能交换 $a$ 中相邻两个数，求能否在 $n^2$ 次操作内使 $a, b$ 相同，如果可以则构造方案。

$1 \leq n \leq 10^3$，$1 \leq a_i, b_i \leq 10^9$。

关键词：构造，选择排序，冒泡排序。

参考难度：橙/黄。

分析：考虑如果存在一个数 $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++)

#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)

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)

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)