车厢重组

题目描述

旧式火车站有一座桥，旋转 180 度可交换相邻两节车厢。给定车厢总数 $n \leq 10000$ 与 $n$ 个互不相同的车厢号，求把车厢按编号升序排好所需的最少旋转次数。

输入：第一行是 $n$ ，第二行是 $n$ 个车厢号。输出：一个整数表示最少次数。

样例输入：

text

1
24
4 3 2 1

样例输出：

text

思路

每次相邻交换使逆序数变化 $\pm 1$ ，目标逆序数为 0，故最少次数等于逆序对数。把车厢号离散化到 $1..n$ 后，从左到右用权值树状数组维护"已出现元素"：对当前排名 $r$ ，先查前缀和得到已出现且不大于它的个数，再用 已出现总数 − 前缀和 得到左边比它大的元素数，累加后把当前元素插入。

参考代码

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

import sys


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

    # 离散化：车厢号两两不同，排名即在排序后序列中的位置，压到 1..n 方便树状数组下标
    rank = {v: i for i, v in enumerate(sorted(a), 1)}

    tree = [0] * (n + 1)  # 树状数组：维护"已出现元素"按排名的计数
    inversions = 0        # 逆序对总数 = 最少旋转次数
    seen = 0              # 已扫过的元素个数

    for x in a:
        i = rank[x]

        # 前缀和：排名 <= i 的已出现元素个数
        prefix = 0
        j = i
        while j:
            prefix += tree[j]
            j -= j & -j
        # 比 x 大的已出现元素 = 它们与 x 各构成一个逆序对
        inversions += seen - prefix

        j = i              # 把 x 计入树状数组
        while j <= n:
            tree[j] += 1
            j += j & -j
        seen += 1

    print(inversions)


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/**
 * 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 08:58
 * update_at: 2026-10-05 08:58
 */
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 10005; // 车厢数上限

int n;
int a[MAXN];       // 原始车厢顺序
int sorted_a[MAXN]; // 用于离散化的副本
int tree[MAXN];    // 权值树状数组：维护已插入元素按排名的计数

// 树状数组前缀和查询：排名 <= x 的已插入元素个数
ll query(int x) {
    ll s = 0;
    for (int i = x; i > 0; i -= i & -i) {
        s += tree[i];
    }
    return s;
}

// 树状数组单点增加：排名为 x 的位置加 1
void add(int x) {
    for (int i = x; i <= n; i += i & -i) {
        tree[i] += 1;
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        sorted_a[i] = a[i];
    }

    // 离散化：把车厢号映射为 1..n 的排名
    sort(sorted_a + 1, sorted_a + n + 1);
    for (int i = 1; i <= n; i++) {
        a[i] = lower_bound(sorted_a + 1, sorted_a + n + 1, a[i]) - sorted_a;
    }

    ll inversions = 0; // 逆序对总数 = 最少旋转次数
    for (int i = 1; i <= n; i++) {
        // 已插入元素总数 - 比 a[i] 小或相等的已插入元素数 = 左边比 a[i] 大的元素数
        inversions += (ll)(i - 1) - query(a[i]);
        add(a[i]); // 把当前元素插入树状数组
    }

    printf("%lld\n", inversions);
    return 0;
}

目录

题目描述

思路

参考代码