P1271 【深基9.例1】选举学生会
题目描述
学校正在选举学生会成员，有 \(n\)（\(1 \le n\le 999\)）名候选人，每名候选人编号分别从 \(1\) 到 \(n\)，现在收集到了 \(m\)（\(1 \le m \le 2000000\)）张选票，每张选票都写了一个候选人编号。现在想把这些堆积如山的选票按照投票数字从小到大排序。设第 \(i\)（\(1 \le i \le m\)）张选票上的数字为 \(a_i\)，则保证有 \(1 \le a_i \le n\)。
输入格式
输入 \(n\) 和 \(m\) 以及 \(m\) 个选票上的数字。
输出格式
求出排序后的选票编号。
输入输出样例 #1
输入 #1
输出 #1
Tip
用快排完全没问题（虽然这题更优是计数排序，但你现在练快排是对的 👍）
📌 题目分析
👉 本质： 对数组进行：
👉 类型： 快速排序（大数据量）
🧠 解题思路（快排版）
1️⃣ 核心建模
输入：
目标：
2️⃣ 为什么可以用快排
- m ≤ 2,000,000（很大）
- 快排平均复杂度：
👉 在优化 IO + 合理 pivot 情况下可以通过
3️⃣ 快排核心
4️⃣ 优化点（这题必须注意‼️）
✅ 1. 快速 IO
✅ 2. pivot 选中间
避免退化
✅ 3. 尽量用数组（不要 vector 慢扩容）
5️⃣ 时间复杂度
💻 C++代码（快排）
#include <bits/stdc++.h>
using namespace std;
const int N = 2000005;
int a[N];
int n, m;
void quick_sort(int l, int r) {
if (l >= r) return;
int i = l, j = r;
int pivot = a[(l + r) >> 1];
while (i <= j) {
while (a[i] < pivot) i++;
while (a[j] > pivot) j--;
if (i <= j) {
swap(a[i], a[j]);
i++, j--;
}
}
if (l < j) quick_sort(l, j);
if (i < r) quick_sort(i, r);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < m; i++) cin >> a[i];
quick_sort(0, m - 1);
for (int i = 0; i < m; i++) {
cout << a[i] << " ";
}
return 0;
}
⚠️ 易错点（这题用快排容易翻车）
❌ 1. 爆栈（递归太深）
👉 数据极端时可能：
👉 解决（进阶）：
- 随机 pivot（高级）
- 或改用
sort
❌ 2. IO 太慢
👉 一定要：