B | Age Sort Input: Standard Input Output: Standard Output |
---|
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.
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.
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.
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
数据大,内存小,而数据值的范围有限,适合运用计数排序求解...
代码:
1 #include<cstdio>
2 #include<cstring>
3 /*计数排序*/
4 int main()
5 {
6 int n,hash[101],val;
7 while(~scanf("%d",&n)&&n)
8 {
9 memset(hash,0,sizeof(hash));
10 for(int i=0;i<n;i++)
11 {
12 scanf("%d",&val);
13 hash[val]++;
14 }
15 int flag=true;
16 for(int i=0; i<=100; i++)
17 {
18 for(int j=1;j<=hash[i];j++)
19 {
20 if(flag)
21 {
22 printf("%d",i);
23 flag=false;
24 }
25 else printf(" %d",i);
26 }
27 }
28 puts("");
29 }
30 return 0;
31 }