UVA之11462 - Age Sort

本文主要是介绍UVA之11462 - Age Sort，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题目】

You are given the ages (in years) of all people of a country with at least 1 year of age. You know that no individual in that country lives for 100 or more years. Now, you are given a very simple task of sorting all the ages in ascending order.

Input

There are multiple test cases in the input file. Each case starts with an integer n (0<n<=2000000), the total number of people. In the next line, there are n integers indicating the ages. Input is terminated with a case where n = 0. This case should not be processed.

Output

For each case, print a line with n space separated integers. These integers are the ages of that country sorted in ascending order.

 

Warning: Input Data is pretty big (~  25 MB) so use faster IO.

Sample Input                             Output for Sample Input

5 3 4 2 1 5 5 2 3 2 3 1 0

1 2 3 4 5 1 2 2 3 3

Note: The memory limit of this problem is 2 Megabyte Only.

Problem Setter: Mohammad Mahmudur Rahman

Special Thanks: Shahriar Manzoor

【分析】

由于数据太大，内存限制太紧（甚至都不能把它们全读进内存），因此无法使用快速排序方法。但整数范围很小，可以用计数排序方法。

【代码】

/*********************************
*   日期：2014-5-2
*   作者：SJF0115
*   题号: 11462 - Age Sort
*   地址：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=26&page=show_problem&problem=2457
*   来源：UVA
*   结果：Accepted
*   总结：计数排序
**********************************/
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;int main(){int i,j,age,n;int count[101];//freopen("C:\\Users\\wt\\Desktop\\acm.txt","r",stdin);while(scanf("%d",&n)!= EOF && n != 0){//初始化memset(count,0,sizeof(count));//统计人数for(i = 0;i < n;i++){scanf("%d",&age);count[age]++;}//按照年龄从小到大输出bool first = true;//标志 控制格式  第一次输出for(i = 1;i < 101;i++){for(j = 0;j < count[i];j++){if(!first){printf(" ");}first = false;printf("%d",i);}}printf("\n");}return 0;
}

如果还要精益求精，可以优化输入输出，进一步降低运行时间。程序如下。

/*********************************
*   日期：2014-5-2
*   作者：SJF0115
*   题号: 11462 - Age Sort
*   地址：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=26&page=show_problem&problem=2457
*   来源：UVA
*   结果：Accepted
*   总结：
**********************************/
#include<cstdio>
#include<cstring>
#include<cctype> 	//为了使用isdigit宏
//内联函数
//逐字符输入
inline int ReadInt(){char c = getchar();while(!isdigit(c)){c = getchar();}int x = 0;while(isdigit(c)){x = x * 10 + c - '0';c = getchar();}return x;
}
//声明成全局变量可以减小开销
int buf[10];
//逐字符输出
inline void WriteInt(int i){int p = 0;//特殊情况：i等于0的时候需要输出0，而不是什么也不输出if(i == 0){p++;}else{//分解为字符while(i){buf[p++] = i % 10;i /= 10;}}//逐字符输出for(int j = p-1; j >=0; j--){//逆序输出putchar('0' + buf[j]);}
}int main() {int n, x, c[101];while(n = ReadInt()){memset(c, 0, sizeof(c));for(int i = 0; i < n; i++) c[ReadInt()]++;//输出int first = 1;for(int i = 1; i <= 100; i++){for(int j = 0; j < c[i]; j++) {if(!first) putchar(' ');first = 0;WriteInt(i);}}putchar('\n');}//whilereturn 0;
}

上述优化使得运行时间缩短了约2/3。一般情况下，当输入输出数据量很大时，应尽量用scanf和printf函数；如果时间效率还不够高，应逐字符输入输出，就像上面的readint和writeint函数。不管怎样，在确信I/O时间成为整个程序性能瓶颈之前，不要盲目优化。测试方法也很简单：输入之后不执行主算法，直接输出一个任意的结果，看看运行时间是否过长。

这篇关于UVA之11462 - Age Sort的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---