三值的排序

题目描述

给定一个长度为 $N$ （ $1 \le N \le 1000$ ）的序列，每个元素只可能是 $1$ 、 $2$ 或 $3$ 。每次操作可以任选两个下标交换它们的值，求把序列排成升序所需的最少交换次数。

输入：第一行一个整数 $N$ ；接下来 $N$ 行每行一个数字。输出：一行一个整数，表示最少交换次数。

样例输入：第一行 9，后面依次 2 2 1 3 3 3 2 3 1（每行一个数）；样例输出：4。

思路

设 $1,2,3$ 的个数为 $c_1,c_2,c_3$ ，排序后的目标区间随之确定，用 $cnt(i,j)$ 表示目标区间 $i$ 的位置上实际放着数字 $j$ 的个数。先做两两直接对换：区间 $i$ 与 $j$ 之间 $\min(cnt(i,j),cnt(j,i))$ 次，每次让两个数同时归位；剩余错位必然构成三元环，每个环需 $2$ 次交换，个数为 $cnt(1,2)-d_{12}$ 与 $cnt(2,1)-d_{12}$ 中非零的那一个，答案即两组对换数之和加 $2\times$ 三元环个数。

参考代码

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-04-18 10:00
# update_at: 2026-04-18 10:00

import sys
from collections import Counter


def count_min_swaps(a: list[int]) -> int:
    """计算将只含 1, 2, 3 的序列排成升序所需的最少交换次数。"""
    c = Counter(a)
    n1, n2 = c[1], c[2]

    # 统计排完序后属于区间 i 的位置上实际出现的数字 j 的数量
    cnt1_in_2 = sum(1 for x in a[n1:n1 + n2] if x == 1)
    cnt2_in_1 = sum(1 for x in a[:n1] if x == 2)
    cnt1_in_3 = sum(1 for x in a[n1 + n2:] if x == 1)
    cnt3_in_1 = sum(1 for x in a[:n1] if x == 3)
    cnt2_in_3 = sum(1 for x in a[n1 + n2:] if x == 2)
    cnt3_in_2 = sum(1 for x in a[n1:n1 + n2] if x == 3)

    # 两两错位直接互换（1 次交换纠正 2 个数）
    direct_12 = min(cnt1_in_2, cnt2_in_1)
    direct_13 = min(cnt1_in_3, cnt3_in_1)
    direct_23 = min(cnt2_in_3, cnt3_in_2)

    # 剩下的错位必然构成 3 元环（2 次交换纠正 3 个数）
    remain = (cnt1_in_2 - direct_12) + (cnt2_in_1 - direct_12)

    return direct_12 + direct_13 + direct_23 + 2 * remain


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data, None)  # 输入只有 n 和后面的 n 个数；空输入按原样直接返回
    if n is None:
        return
    a = [next(data) for _ in range(n)]
    print(count_min_swaps(a))


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/**
 * 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 09:46
 * update_at: 2026-10-06 09:46
 */

// main.cpp：三值的排序（USACO sort3）
// 做法：先按 1/2/3 的个数把位置划成三个目标区间，
// 优先做两两直接对换（1 次交换归位 2 个数），
// 剩下的错位必然构成三元环，每个环需要 2 次交换。

#include <cstdio>
#include <algorithm>

typedef long long ll;

const int MAXN = 1005;

ll n;                 // 序列长度
ll a[MAXN];           // a[i]：第 i 个位置上的数字（1/2/3）
ll cnt[4];            // cnt[v]：数字 v 的总个数
ll miss[4][4];        // miss[i][j]：目标区间 i 的位置上实际放着数字 j 的个数

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

    // 统计每个数字的总个数，确定三个目标区间的边界
    for (ll i = 1; i <= n; ++i)
        ++cnt[a[i]];

    // 扫描一遍统计错位分布：位置落在哪个目标区间，上面放的却是哪个数字
    ll pos = 0; // 当前位置（1 开始），顺便用它判断属于哪个目标区间
    for (ll i = 1; i <= n; ++i) {
        ++pos;
        ll region; // 该位置排序后应属于的区间编号（1/2/3）
        if (pos <= cnt[1]) region = 1;
        else if (pos <= cnt[1] + cnt[2]) region = 2;
        else region = 3;
        if (region != a[i])
            ++miss[region][a[i]];
    }

    // 第一步：两两直接对换，min(cnt(i,j), cnt(j,i)) 次即可消掉这些对
    ll d12 = std::min(miss[1][2], miss[2][1]);
    ll d13 = std::min(miss[1][3], miss[3][1]);
    ll d23 = std::min(miss[2][3], miss[3][2]);

    // 第二步：剩余错位构成三元环 1->2->3->1（或反向），每个环 2 次交换
    ll remain = (miss[1][2] - d12) + (miss[2][1] - d12);

    printf("%lld\n", d12 + d13 + d23 + remain * 2);
    return 0;
}

目录

题目描述

思路

参考代码