【例7.7】光荣的梦想

题目描述

给定长度为 $n$ 的数列，每次只能交换相邻两个元素，求把数列排成升序所需的最少交换次数。输入第一行 $n$ ，第二行 $n$ 个整数（ $n \le 10000$ ）；输出最少交换次数。样例输入 4 / 2 1 4 3，样例输出 2。

思路

每次相邻交换最多消除一个逆序对，而数列无序时总能找到相邻逆序对进行交换，所以最少交换次数恰好等于逆序对数。用归并排序边归并边统计：右半元素出队时，左半剩余元素都比它大，累加左半剩余个数即可，复杂度 $O(n \log n)$ 。

参考代码

Python 版：

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#!/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-09-30 05:32
# update_at: 2026-09-30 05:32

import sys


def sort_count(seg: list[int]) -> tuple[list[int], int]:
    """归并排序同时数逆序对：返回 (有序序列, 段内逆序对数)。

    逆序对即下标递增而数值严格递减的数对；每次相邻交换恰好消除一个逆序对，
    且逆序对数是交换次数的下界，故最少交换次数就是逆序对总数。
    """
    if len(seg) < 2:
        return seg, 0
    mid = len(seg) // 2
    left, left_inv = sort_count(seg[:mid])
    right, right_inv = sort_count(seg[mid:])

    merged: list[int] = []
    inv = left_inv + right_inv
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:  # 相等时先取左半，保持稳定、不把相等计成逆序
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
            inv += len(left) - i  # 左半剩余元素都比当前右半元素大，各配成一个逆序对
    merged += left[i:] + right[j:]
    return merged, inv


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    seq = [next(data) for _ in range(n)]
    print(sort_count(seq)[1])


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74/**
 * 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-05 09:49
 * update_at: 2026-10-05 09:49
 */
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 10005;

ll a[MAXN];   // a[1..n] 原数列
ll tmp[MAXN]; // 归并排序的临时存放数组
ll ans;       // 逆序对总数，也就是最少相邻交换次数

// 归并排序 [left, right]，同时统计跨段逆序对
void merge_sort(int left, int right) {
    if (left >= right) {
        return;
    }
    int mid = (left + right) / 2;
    merge_sort(left, mid);
    merge_sort(mid + 1, right);

    int i = left;
    int j = mid + 1;
    int k = left;
    while (i <= mid && j <= right) {
        if (a[i] <= a[j]) {
            // 相等时先取左半，不把相等元素算成逆序对
            tmp[k] = a[i];
            i++;
            k++;
        } else {
            tmp[k] = a[j];
            j++;
            k++;
            ans += mid - i + 1; // 左半剩余元素都比 a[j] 大，各配成一个逆序对
        }
    }
    while (i <= mid) {
        tmp[k] = a[i];
        i++;
        k++;
    }
    while (j <= right) {
        tmp[k] = a[j];
        j++;
        k++;
    }
    for (int p = left; p <= right; p++) {
        a[p] = tmp[p];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    ans = 0;
    merge_sort(1, n);
    cout << ans << "\n";

    return 0;
}

【例7.7】光荣的梦想

目录

题目描述

思路

参考代码