洛谷 P1271 题解
看完点个赞,谢谢!
P1271
题目描述
学校正在选举学生会成员,有 n(n≤999)名候选人,每名候选人编号分别从 1 到 n,现在收集到了 m(m<=2000000) 张选票,每张选票都写了一个候选人编号。现在想把这些堆积如山的选票按照投票数字从小到大排序。
输入格式
输入 nn 和 mm 以及 mm 个选票上的数字。
输出格式
求出排序后的选票编号。
Input 输入
5 102 5 2 2 5 2 2 2 1 2
Output 输出
1 2 2 2 2 2 2 2 5 5
这题一看就是个排序题。
先说说各个排序算法的最大可排序元素数量(1秒内)
1 选择排序、插入排序、冒泡排序:10000次
时间复杂度:
百度百科 时间复杂度
2 快速排序、sort 函数排序:100000次
时间复杂度:
3 堆排序、桶排序、基数排序、计数排序 100000000次
时间复杂度:
堆排序参考:https://www.cnblogs.com/chengxiao/p/6129630.html
桶排序参考:https://blog.csdn.net/weixin_38426554/article/details/95931499
基数排序简单说就是一个数当基数,然后围绕那个数展开排序算法。
但是以上都不是这题要用的方法,下面才是
计数排序!
计数排序主要用在那种范围小但数数的个数超级多时使用
比如在 [1, 100] 的区间里有 50000 个数,这时就该用计数排序
说回那道题直接计数排序就行了。
那它是怎么实现的呢?
首先读入很多的数,然后读入时记录它是多少,这是需要一个计数的数组,比如 cnt。然后让那个数所对应的 cnt 数组的位置+1,(其实目的就是为了找出每个数输入了几次)。
接着输出时,比如从小到大输出,就可以看看最小的数出现了多少次,比如2次,假如最小数是1,那么就输出两个1,然后看2有多少个就输出多少个2,以此类推,知道输出完了所有数就OK。
以上就是大概的思路
现在给个程序:
注意:此题数据量极大,需用加速 cin 与 cout 的东西
ios::sync_with_stdio(0);
cin.tie(0);
可参考:https://blog.csdn.net/zeekliu/article/details/124077201
//LG1271 21-07-30#include using namespace std;int main(){ ios::sync_with_stdio(0); cin.tie(0); int n,m; int a[2000001],p[1000]; memset(p,0,sizeof(p)); cin>>n>>m; for (int i=1;i>a[i];p[a[i]]++; } for (int i=1;i<=n;i++) { for (int j=1;j<=p[i];j++) cout<<i<<" "; } return 0;}