http://acm.nyist.net/JudgeOnline/problem.php?pid=673

悟空的难题

时间限制：1000 ms  |  内存限制：65535 KB

难度：2

 

描述

 

自从悟空当上了齐天大圣，花果山上的猴子猴孙们便也可以尝到天上的各种仙果神酒，所以猴子猴孙们的体质也得到了很好的提高，身高年龄也得到了很大的提升。有一天悟空没事，要带领他的猴子猴孙们出去旅游，为了保持花果山的形象，一位年长的猴子建议猴子们都按身高排成一队。

猴子们是如此的着急出发，如何快速的排好队伍让这个神功盖世的齐天大圣头痛不已。现在请你来当齐天大圣悟空的军师来帮他排序吧。

 

 

 

输入

数据第一行包括一个整数t(0<t<=50)，代表有t组测试数据；

接下来的每组数据第一行有两个整数，n，m(0<n<=1000000)，分别代表猴子的数量和最高身高（身高按厘米来记，假设所有猴子身高最多不会超过1米）。第二行为n个猴子的身高，空格隔开。

输出

每组输出一行。

从小到大输出所有猴子的身高，用空格隔开。（最后一个身高后面没有空格）。

样例输入

25 1002 4 5 1 310 1009 8 5 1 10 2 3 4 9 8

样例输出

1 2 3 4 51 2 3 4 5 8 8 9 9 10 分析：

排序。不过用一般的方法都会超时，不管是冒泡，qsort，还是sort。

唯一的办法是利用数组的下标标记排序。

因为猴子的身高不超过100，。可以建一个 [100]的数组，只需标记出每个身高各有多少只猴子就行了。

AC代码：

1 #include
       
         2 int main()  3 {  4 int k; 5 scanf ("%d", &k); 6 while (k--)  7 { 8     int m, n, b, j,i; 9     int a[101] = {
     0};10     scanf ("%d%d", &m,&n);11     for (i = 0; i < m; i++) 12     {13     scanf("%d", &b);14     a[b]++;15     }16     for (i = 0; i <= n; i++)17     {18         while (a[i]--) 19             printf("%d ", i);20     }21 printf("\n");22 }