首页 > 其他分享 >P1271 【深基9.例1】选举学生会

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

时间:2024-02-07 20:33:59浏览次数:30  
标签:输出 int 深基 选票 数组 P1271 排序 学生会

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

相关文章

  • P5711 【深基3.例3】闰年判断
    题目写在开头:本题并不容易出错,但是需要一些常识,记录的目的也只是为了代码优化原题目位于:[P5711【深基3.例3】闰年判断-洛谷|计算机科学教育新生态(luogu.com.cn)]【深基3.例3】闰年判断题目描述输入一个年份,判断这一年是否是闰年,如果是输出$1$,否则输出$0$。输入格式......
  • P2433 【深基1-2】小学数学 N 合一
    题目原题目在[P2433【深基1-2】小学数学N合一-洛谷|计算机科学教育新生态(luogu.com.cn)]【深基1-2】小学数学N合一题目描述问题1请输出IloveLuogu!问题2这里有$10$个苹果,小A拿走了$2$个,Uim拿走了$4$个,八尾勇拿走剩下的所有的苹果。我们想知道:小......
  • 【洛谷 P2249】【深基13.例1】查找(向量+二分查找+递归)
    【深基13.例1】查找题目描述输入个不超过的单调不减的(就是后面的数字不小于前面的数字)非负整数,然后进行次询问。对于每次询问,给出一个整数,要求输出这个数字在序列中第一次出现的编号,如果没有找到的话输出。输入格式第一行个整数和,表示数字个数和询问次数。第二行......
  • 【洛谷 P2249】【深基13.例1】查找(向量+lower_bound)
    【深基13.例1】查找题目描述输入个不超过的单调不减的(就是后面的数字不小于前面的数字)非负整数,然后进行次询问。对于每次询问,给出一个整数,要求输出这个数字在序列中第一次出现的编号,如果没有找到的话输出。输入格式第一行个整数和,表示数字个数和询问次数。第二行......
  • 洛谷题单指南-排序-P1923 【深基9.例4】求第 k 小的数
    原题链接:https://www.luogu.com.cn/problem/P1923题意解读:要最快的求第k小的数,O(n)的做法是利用快排的思想对数据进行划分第一步、取分界点x,通常设x=a[(l+r)/2]第二步、将小于x的挪到x左边,将大于x的挪到x右边第三步、比较,如果x左边的个数大于k,则继续递归处理左边,否则递......
  • P5739 【深基7.例7】计算阶乘
    1.题目介绍【深基7.例7】计算阶乘题目描述求\(n!\),也就是\(1\times2\times3\dots\timesn\)。挑战:尝试不使用循环语句(for、while)完成这个任务。输入格式第一行输入一个正整数\(n\)。输出格式输出一个正整数,表示\(n!\)。样例#1样例输入#13样例输出#16提示......
  • P5738 【深基7.例4】歌唱比赛
    1.题目介绍【深基7.例4】歌唱比赛题目描述\(n(n\le100)\)名同学参加歌唱比赛,并接受\(m(m\le20)\)名评委的评分,评分范围是\(0\)到\(10\)分。这名同学的得分就是这些评委给分中去掉一个最高分,去掉一个最低分,剩下\(m-2\)个评分的平均数。请问得分最高的同学分数是多少?......
  • P5737 【深基7.例3】闰年展示
    1.题目介绍【深基7.例3】闰年展示题目描述输入\(x,y\),输出\([x,y]\)区间中闰年个数,并在下一行输出所有闰年年份数字,使用空格隔开。输入格式输入两个正整数\(x,y\),以空格隔开。输出格式第一行输出一个正整数,表示\([x,y]\)区间中闰年个数。第二行输出若干个正整数,按照......
  • P5736 【深基7.例2】质数筛
    1.题目介绍【深基7.例2】质数筛题目描述输入\(n\)个不大于\(10^5\)的正整数。要求全部储存在数组中,去除掉不是质数的数字,依次输出剩余的质数。输入格式第一行输入一个正整数\(n\),表示整数个数。第二行输入\(n\)个正整数\(a_i\),以空格隔开。输出格式输出一行,依次输......
  • 洛谷题单指南-排序-P1271 【深基9.例1】选举学生会
    原题链接:https://www.luogu.com.cn/problem/P1271题意解读:最直接的计数排序问题,借助一个桶h[N],对被投票的候选人x执行h[x]++,再按顺序遍历输出即可。100分代码:#include<bits/stdc++.h>usingnamespacestd;constintN=1005;inth[N];intmain(){intn,m;......