形式化题目

给定一个含 $n$ 个互不相同整数的序列 $a_1, a_2, \ldots, a_n$。每次操作只能交换相邻的两个元素，目标是把序列排成严格升序。求最少操作次数。

多个用例依次给出，读到 $n = 0$ 时终止。$n < 5 \times 10^5$，$0 \le a_i \le 999999999$。

正解

思路

一句话本质：只交换相邻元素的排序，最少交换次数就等于序列的逆序对数——用归并排序在合并两个有序半段时顺便把逆序对数统计出来，复杂度 $O(n \log n)$。

先看朴素做法：既然每次交换只动相邻两个元素，那就模拟冒泡，或者干脆双重循环枚举所有对 $(i, j)$，数一数有多少个 $i < j$ 且 $a_i > a_j$。$n < 5 \times 10^5$ 时这样的 $O(n^2)$ 枚举约 $1.25 \times 10^{11}$ 对，必然超时。瓶颈在于：每一对元素的关系被重复看了一遍又一遍，而交换的过程根本不需要真的模拟。

为什么答案是逆序对数？ 逆序对指满足 $i < j$ 且 $a_i > a_j$ 的下标对。观察一次相邻交换 $a_i \leftrightarrow a_{i+1}$（不妨 $a_i > a_{i+1}$）：

• 对其他任何元素 $a_k$，它与 $a_i$、$a_{i+1}$ 的相对左右位置都没变，逆序状态不变；
• 唯一变化的是这一对本身：从"逆序"变成"有序"，逆序对数恰好减 1。

所以任何排序方案的交换次数 $\geqslant$ 初始逆序对数（每次交换最多消掉 1 个逆序对，而升序序列逆序对数为 0）；冒泡排序的每次交换消掉的又恰好是 1 个，能取到这个下界。最少交换次数 = 初始逆序对数，连交换的具体位置都不用关心。

问题？ 怎么在 $O(n \log n)$ 内数出逆序对？

分治。按位置把序列切成左右两半，逆序对 $(i, j)$ 分成三类：

前两类交给递归。关键是第三类：先让左右两半各自有序，再归并合并。合并时两个指针分别扫左半 $buf[i]$ 与右半 $buf[j]$，一旦右半的 $buf[j]$ 更小、需要先进入结果，就说明左半还没被取走的 $mid - i$ 个元素全都大于 $buf[j]$（左半已有序），它们各自与 $buf[j]$ 构成一个跨中线逆序对——一次减法就把这一整段计数完毕，不用逐对枚举。

用样例序列 $9\ 1\ 0\ 5\ 4$ 看整个分治结构（每个节点标出该层的合并与跨中线贡献）：

flowchart TD
    A["原始: 9 1 0 5 4"] --> B["左半 [0,2): 9 1"]
    A --> C["右半 [2,5): 0 5 4"]
    B --> D["合并 9 与 1:<br/>1 取出 9 → +1<br/>有序: 1 9"]
    C --> E["[5 4] 合并:<br/>4 取出 5 → +1<br/>再与 0 合并 → +0<br/>有序: 0 4 5"]
    D --> F["顶层合并 [1 9] 与 [0 4 5]:<br/>0 取出 (1,9) → +2<br/>4 取出 9 → +1<br/>5 取出 9 → +1<br/>跨线共 +4"]
    E --> F
    F --> G["有序: 0 1 4 5 9<br/>合计 1 + 1 + 4 = 6 ✓"]

顶层合并的精算（左半有序 $[1, 9]$，右半有序 $[0, 4, 5]$）——「取出」后括号里是被它跳过的左半剩余元素：

顶层跨线共 $2 + 1 + 1 = 4$，加上左半内部的 $1$ 与右半内部的 $1$，答案 $6$ ✓。第二个用例 $1\ 2\ 3$ 已然有序，无任何逆序对，输出 $0$ ✓。

实现细节：

• 递归函数 inversions(lo, hi) 返回 $a_{lo..hi-1}$ 的逆序对数：区间长度 $\le 1$ 直接返回 0，否则 = 左递归 + 右递归 + merge_count(...)。
• 合并用预分配缓冲区 buf：先把 a[lo:hi] 整段拷进 buf，再双指针写回 a，保证归并后该段有序、不影响上层统计。
• 判断"取左半"的条件是 buf[i] <= buf[j]：本题元素互不相同，取不取等号不影响计数，但写 <= 让相等元素保持稳定，通用性更好。
• 答案上界是 $\binom{n}{2} \approx 1.25 \times 10^{11}$，C++ 需要 long long；Python 的 int 天然无溢出。
• 多用例读到 $n = 0$ 为止：一次性读入全部 token，逐用例迭代解析。

另一条等价路线是树状数组 + 离散化：值域高达 $10^9$，先把权值映射到排名，再从左往右插入，每个元素查询"已插入的数里比它大的个数"（或倒序查"比它小的个数"），复杂度同为 $O(n \log n)$。本文选归并：不需要离散化，代码也更短。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 10:13
# update_at: 2026-10-01 10:13

import sys
from collections.abc import Iterator


def merge_count(a: list[int], buf: list[int], lo: int, mid: int, hi: int) -> int:
    """合并有序的 a[lo:mid] 与 a[mid:hi]，返回跨中线的逆序对数，并就地排好。"""
    buf[lo:hi] = a[lo:hi]
    i, j, cross = lo, mid, 0
    for k in range(lo, hi):
        if j >= hi or (i < mid and buf[i] <= buf[j]):
            a[k] = buf[i]
            i += 1
        else:
            a[k] = buf[j]
            j += 1
            cross += mid - i  # buf[j] 跳过的是右半还在等待的所有左半元素
    return cross


def inversions(a: list[int], lo: int, hi: int, buf: list[int]) -> int:
    """统计 a[lo:hi] 的逆序对数：左内部 + 右内部 + 跨中线，归并排序一趟完成。"""
    if hi - lo <= 1:
        return 0
    mid = (lo + hi) // 2
    return inversions(a, lo, mid, buf) + inversions(a, mid, hi, buf) \
        + merge_count(a, buf, lo, mid, hi)


def answers(tokens: Iterator[int]) -> Iterator[str]:
    """依次处理每个用例，产出每个序列的最小交换次数。"""
    for n in tokens:
        if n == 0:  # 终止用例
            return
        a = [next(tokens) for _ in range(n)]
        yield str(inversions(a, 0, n, [0] * n))


def solve() -> None:
    tokens = iter(map(int, sys.stdin.buffer.read().split()))
    print('\n'.join(answers(tokens)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 14:05
 * update_at: 2026-10-06 14:05
 */
#include <cstdio>

typedef long long ll;

const int MAXN = 500005; // n < 5e5，数组开到 5e5+5 即可
ll a[MAXN];              // 当前用例的序列
ll buf[MAXN];            // 归并排序使用的缓冲区

// 合并有序的 a[lo..mid-1] 与 a[mid..hi-1]，返回跨中线的逆序对数，并就地排好序。
ll merge_count(int lo, int mid, int hi) {
    for (int i = lo; i < hi; i++) {
        buf[i] = a[i];
    }
    int i = lo;
    int j = mid;
    ll cross = 0;
    for (int k = lo; k < hi; k++) {
        if (j >= hi || (i < mid && buf[i] <= buf[j])) {
            a[k] = buf[i];
            i++;
        } else {
            a[k] = buf[j];
            j++;
            cross += mid - i; // buf[j] 比左半还没被取走的所有元素都小
        }
    }
    return cross;
}

// 统计 a[lo..hi-1] 的逆序对数：左半内部 + 右半内部 + 跨中线。
ll inversions(int lo, int hi) {
    if (hi - lo <= 1) {
        return 0;
    }
    int mid = (lo + hi) / 2;
    ll left = inversions(lo, mid);
    ll right = inversions(mid, hi);
    ll cross = merge_count(lo, mid, hi);
    return left + right + cross;
}

int main() {
    int n;
    while (scanf("%d", &n) == 1 && n != 0) {
        for (int i = 0; i < n; i++) {
            scanf("%lld", &a[i]);
        }
        printf("%lld\n", inversions(0, n));
    }
    return 0;
}

复杂度

设单个用例长度为 $n$。

• 时间：$O(n \log n)$。递归满足 $T(n) = 2T(n/2) + O(n)$，正是归并排序的标准递推；合并中"一次减法统计一段"保证了合并本身是线性开销。
• 空间：$O(n)$——原数组、等长缓冲区 buf，外加 $O(\log n)$ 的递归栈。
• 所有元素互不相同，无需离散化；$n = 5 \times 10^5$ 时 Python 侧存在超时风险（本地实测含读入约 0.7s，接近 OJ 1s 限时），但算法与 C++ 正解同阶，同样的逻辑用 C++ 落地即稳过。

总结

• 相邻交换排序的最少交换次数 = 逆序对数：一次相邻交换恰消 1 个逆序对，升序终态逆序对数为 0，下界可达。
• 归并排序统计逆序对：逆序对按位置分三类，前两类递归，跨中线的一类在合并两个有序半段时由"右半取出一个元素 → 左半剩余全部比它大"一次性计 $mid - i$ 个。
• 复杂度 $O(n \log n)$ / $O(n)$，是逆序对问题的通用套路；等价替代是树状数组 + 离散化。
• 大答案要当心：$n(n-1)/2$ 在 $n = 5 \times 10^5$ 时超出 32 位整数范围。