【计数排序与初级排序】GESP四级 / CSP-J 题解：luogu-P1271 【深基9.例1】选举学生会

洛谷 P1271【深基9.例1】选举学生会。本题出自《深入浅出程序设计竞赛 - 基础篇》，是学习计数排序（Counting Sort / 桶排序思想）与非比较排序算法的标志性入门经典试题，被标准收录于 CCF GESP 四级认证考纲（初级排序考点）及 CSP-J 普及组核心必做题单。题目核心考点在于突破传统基于比较的 $\mathcal{O}(m \log m)$ 排序思维瓶颈，利用“候选人编号值域小（$n \le 999$）而选票样本总量极大（$m \le 2 \times 10^6$）”这一关键数据特征，采用频数统计数组实现 $\mathcal{O}(m + n)$ 线性时间与 $\mathcal{O}(n)$ 极小内存的优化解法。题目难度⭐☆☆☆☆，洛谷难度等级评定为入门。

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

🔗 洛谷原题传送门：luogu-P1271 【深基9.例1】选举学生会

题目要求

题目描述

学校正在选举学生会成员，有 $n(n \le 999)$ 名候选人，每名候选人编号分别从 $1$ 到 $n$，现在收集到了 $m(m \le 2000000)$ 张选票，每张选票都写了一个候选人编号。现在想把这些堆积如山的选票按照投票数字从小到大排序。

输入格式

输入 $n$ 和 $m$ 以及 $m$ 个选票上的数字。

输出格式

求出排序后的选票编号。

输入输出样例 #1

样例输入 #1

5 10
2 5 2 2 5 2 2 2 1 2

样例输出 #1

1 2 2 2 2 2 2 2 5 5

说明/提示

对于 $100\%$ 的数据，$1 \le n \le 999$，$1 \le m \le 2 \times 10^6$。

题目深度剖析

1. 数据规模与算法博弈

在算法竞赛与等级考试中，审题的第一步是观察数据规模与值域边界：

• 候选人编号上限：$n \le 999$（值域极小，严格落在 $[1, 999]$ 之间）；
• 选票总数：$m \le 2 \times 10^6$（数据量极大，达到两百万级）。

针对该数据特征，我们可以对比两种解题路线：

2. 计数排序（Counting Sort）核心原理

计数排序是一种基于散列（Hash）与频数统计思想的非比较排序算法：

1. 建立频数桶：定义全局数组 int cnt[MAXN];，其中 cnt[i] 表示编号为 $i$ 的候选人目前一共获得了多少张选票；
2. 扫描与统计（投票入桶）：依次读入 $m$ 张选票上的候选人编号 $x$，每读入一个数就执行 cnt[x]++。扫描一遍输入流后，所有候选人的得票总数均已统计完毕；
3. 有序展开输出（按号放票）：按照候选人编号升序从小到大依次枚举 $i \in [1, n]$。若候选人 $i$ 获得了 cnt[i] 张票，则连续输出 cnt[i] 个数字 $i$。

由于我们从编号 $1$ 开始按顺序遍历到 $n$，因此输出的所有选票自然而然地满足了由小到大的升序要求，完全避免了元素两两之间的比较与频繁移动！

3. 规范避坑与实现细节

1. 避免局部变长数组（VLA）：
   • 在 C++11 和信奥考纲规范下，严禁在函数内编写形如 int cnt[n + 1]; 的局部变长数组；
   • 规范做法是在全局数据段定义常量 const int MAXN = 1005; 并声明静态全局数组 int cnt[MAXN];，全局数组在程序加载时自动完成零初始化。
2. 输出格式控制：
   • 题目样例输出中各个数字以空格分隔。使用布尔标记 bool is_first = true; 控制输出：第一个输出的数字前不加空格，后续每个数字前打印一个空格，末尾输出换行符。
3. 标准输入输出流纯粹性：
   • 严格遵循竞赛规范，直接读入输入数据，不写多余的防御性读入判断；
   • 逻辑自然清晰，适合初学者建立稳固的算法基本功。

完整参考代码 (C++11)

/**
 * Problem: luogu-P1271 【深基9.例1】选举学生会
 * Algorithm: 计数排序 (Counting Sort) 与初级排序
 * Standard: C++11 (CCF GESP 官方大纲规范)
 * Author: OneCoder
 */

#include <iostream>

using namespace std;

// 计数数组（桶）：由于候选人编号范围是 1 ~ n，且 n <= 999
// 在全局数据区定义静态数组，大小开至 1005，自动零初始化，杜绝函数内使用局部变长数组 (VLA)
const int MAXN = 1005;
int cnt[MAXN];

int main() {
    int n, m;
    // 读入候选人数量 n 与选票总数 m
    cin >> n >> m;

    // 循环读入 m 张选票，在对应候选人编号的桶中累加得票数
    for (int i = 0; i < m; ++i) {
        int vote;
        cin >> vote;
        cnt[vote]++;
    }

    // 按照候选人编号从 1 到 n 升序遍历，展开输出所有选票
    bool is_first = true; // 用于精准控制数字之间的空格分隔
    for (int i = 1; i <= n; ++i) {
        // 当候选人 i 仍有剩余票数时，持续输出编号 i
        while (cnt[i] > 0) {
            if (!is_first) {
                cout << " ";
            }
            cout << i;
            is_first = false;
            cnt[i]--; // 票数递减
        }
    }
    cout << "\n";

    return 0;
}

复杂度深度分析

• 时间复杂度：
  • 数据读入与频次累加：遍历读入 $m$ 张选票并更新计数，耗时 $\mathcal{O}(m)$；
  • 结果输出：外层循环遍历 $n$ 个候选人，内层 while 循环的总执行次数恰好等于总票数 $m$，耗时 $\mathcal{O}(n + m)$；
  • 综合时间复杂度为 $\mathcal{O}(m + n)$。在最坏数据规模 $m = 2 \times 10^6, n = 999$ 时，总操作次数仅约 $2 \times 10^6$ 次，耗时约为 $0.35\text{ s}$，极其宽裕地通过时限要求。
• 空间复杂度：
  • 全局计数数组大小为 $1005 \times \text{sizeof(int)} \approx 4\text{ KB}$；
  • 综合空间复杂度为 $\mathcal{O}(n)$，在 $m = 2 \times 10^6$ 的海量选票下几乎不占用内存，远优于保存全部选票所需的 $\mathcal{O}(m)$（约 $8\text{ MB}$）。

总结与同类考点拓展

“选举学生会”是非比较类排序思想的经典启蒙题。解决此类问题的核心启示在于：

1. 值域敏感性：当待排序数据的取值范围（$n$）远小于数据总量（$m$）时，优先考虑计数排序或桶排序；
2. 空间换时间：通过数组下标与元素数值的直接映射，将排序的时间下界由比较排序的 $\mathcal{O}(m \log m)$ 突破至线性时间 $\mathcal{O}(m + n)$；
3. 稳定性与扩展：基础计数排序通过前缀和优化还可以实现稳定排序（Stable Sort），广泛应用于基数排序（Radix Sort）的内部子过程。

经典同类推荐练习题：

• luogu-P1059 [NOIP 2006 普及组] 明明的随机数（桶计数去重与排序）
• luogu-P1177 【模板】排序（初级与高级排序综合对比）
• luogu-P1104 生日（初级多关键字排序）