【Java】P1271选举学生会—桶排序&Java快速读写IO—（洛谷OJ）

vlambda
2020-09-03

【Java】P1271选举学生会—桶排序&Java快速读写IO—（洛谷OJ）

点击上方“蓝字”关注我们吧！

题目

题目来源：洛谷OJ

题目链接：

https://www.luogu.com.cn/problem/P1271

题目描述

学校正在选举学生会成员，有n(n≤999) 名候选人，每名候选人编号分别从 1 到 nn，现在收集到了 m(m<=2000000) 张选票，每张选票都写了一个候选人编号。现在想把这些堆积如山的选票按照投票数字从小到大排序。输入 n 和 m 以及 m个选票上的数字，求出排序后的选票编号。

输入格式

无

输出格式

无

输入输出样例

输入 #1

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

输出 #1

 1 2 2 2 2 2 2 2 5 5

思路

首先，我们要确定用什么排序方法，通过分析题目，我们会想到在《啊哈算法》里面第一篇就提到的桶排序
对桶排序不熟悉的童鞋，可以先看看我的这一篇文章
【Java】P1047 校门外的树—算法：桶排序—（OJ：洛谷）

https://blog.csdn.net/weixin_43785855/article/details/10295335

当然，只是简单的桶排序无法解决这么大数据下的内存限制，所以我们还要采用Java快速读写IO
对Java快速读写IO不熟悉的童鞋，可以先看看我的这一篇文章
【Java】快速读写IO模板

https://blog.csdn.net/weixin_43785855/article/details/107134525

Java源码

package 算法1_2排序;
import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.io.PrintWriter;import java.io.StreamTokenizer;
/** *@Title P1271选举学生会.java *@description TODO *@time 2020年7月3日 *@author Baisu *@version 1.0 */public class P1271选举学生会 {
 public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StreamTokenizer in = new StreamTokenizer(br); PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); in.nextToken(); int n = (int)in.nval; in.nextToken(); int m = (int)in.nval; int[] book = new int [999]; for(int i=0; i<m; i++) { in.nextToken(); book[(int)in.nval-1]++; } for(int i=0; i<n; i++) { while(book[i]--!=0) { pr.print(i+1+" "); } } pr.flush(); }}