1.题目介绍
【深基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
2.题解
2.1 排序
思路
这里我们很容易想到用一个数组记录每张选票上的值,然后再将这个数组排序后输出。
但是有一个更简单的方法,因为最后我们知道选票最后是按学生序号依次输出的,那我们的数组就不用来记录选票号,而是记录每个序号学生得到了几张票,而学生序号已经记录在了索引中,后面我们直接根据记录数,输出n次序号即可。
代码
注意这里序号是从1开始到n,数组大小应设置为n+1,多预留出一个空间。
这种排序方法被称为计数排序。读入选票并统计的时间复杂度是0(m),输出选票的时间复杂度是0(m+n)²,空间复杂度是0(n)。所以计数排序只能用于排序编号(值域)范围不是很大的数字。如果需要排序的数字要到\(10^9\)那么别说运行时间了,内存都无法存得下这么大的范围的数组。此外,所以就不能使用这种算法了。
不过也有改进方法,比如桶排序和基数排序(不要和计数排序弄混了)使用类似的思路,但
是相对比较复杂,限于篇幅不在这里介绍。无论是计数排序、桶排序,还是基数排序,这些排序算法都是基于分类而非基于比较的排序,不依赖排序对象之间的直接大小比较。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n, m;
cin >> n >> m;
vector<int> stu(n + 1, 0);
for(int i = 0; i < m; i++){
int tmp;
cin >> tmp;
stu[tmp]++;
}
for(int i = 1; i <= n; i++){
for(int j = 0; j < stu[i]; j++){
cout << i << ' ';
}
}
}
标签:输出,int,深基,选票,数组,P1271,排序,学生会
From: https://www.cnblogs.com/trmbh12/p/18011261