【深基9.例1】选举学生会

题意

给出 m 张选票，每张票是 1..n 之间的候选人编号。要求把所有选票编号从小到大输出。

思路

虽然票数最多有 2,000,000，但候选人编号最多只有 999。可以使用计数排序：

count[x] 记录编号 x 出现次数；
从 1 到 n 枚举候选人编号；
每个编号输出 count[x] 次。

这比直接排序更能体现“值域小”的优势。

Python 知识

/home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：计数数组适合值域较小的频率统计。
/home/rainboy/mycode/hugo-blog/content/program_language/python/oj_input_output_cheatsheet.md：大量输入用 sys.stdin.buffer.read() 更稳。
answer.extend([str(candidate)] * count[candidate]) 批量追加重复编号。
"\n".join(...) 或 " ".join(...) 适合集中输出。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17import sys


data = list(map(int, sys.stdin.buffer.read().split()))
n = data[0]
m = data[1]
votes = data[2:]

count = [0] * (n + 1)
for vote in votes:
    count[vote] += 1

answer = []
for candidate in range(1, n + 1):
    answer.extend([str(candidate)] * count[candidate])

print(" ".join(answer))

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/**
 * 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-07-27 00:00
 * update_at: 2026-07-27 00:00
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005; // 候选人编号最大值

int n, m;
int cnt[MAXN]; // 计数数组，cnt[x] 表示编号 x 获得的票数

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

    cin >> n >> m;

    // 统计每张票
    for (int i = 0; i < m; i++) {
        int vote;
        cin >> vote;
        cnt[vote]++;
    }

    // 按编号从小到大展开输出
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < cnt[i]; j++) {
            cout << i << " ";
        }
    }
    cout << "\n";

    return 0;
}

复杂度

统计 m 张票，展开 m 个结果，时间复杂度是 $O(n+m)$ ，空间复杂度是 $O(n+m)$ 。

总结

当待排序元素值域很小、数量很大时，计数排序比比较排序更直接。

【深基9.例1】选举学生会

目录

题意

思路

Python 知识

代码

复杂度

总结