ACM_排序

除了sort，你还会什么

Time Limit: 1000/500ms (Java/Others)

Problem Description:

给出若干人的年龄（1~100之间的整数），把它们按照从小到大的顺序输出。

Input:

输入包含多组测试数据。每组数据的第一行为一整数 n,(0<n<=2 000 000),即居民总数；下一行输入 n 个整数，表示各居民的年龄。（输入文件约有20 MB,而内存限制只有2 MB,除了sort(),你还会什么...）

Output:

对于每一组数据，按照从小到大的顺序输出各居民的年龄。相邻年龄用空格隔开。

Sample Input:

3
56 56 56
5
99 91 89 63 91

Sample Output:

56 56 56 
63 89 91 91 99 
解题思路：题目中给出n的最大值为2*10^6,也就是直接调用sort函数的话，会超时，因为其时间复杂度是O(nlogn),但是给出的年龄范围只有1~100，相对n来说很小，也就是说我们可以利用一个数组来存相同年龄的人数，然后从1~100顺序遍历输出即可，注意要用C语言的输入输出，不然会超时！！！
AC代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,x,a[101];
    while(~scanf("%d",&n)){
        memset(a,0,sizeof(a));
        for(int i=1;i<=n;++i){
            scanf("%d",&x);a[x]++;
        }
        for(int i=1,m=0;i<=100;++i){
            for(int j=1;j<=a[i];++j){
                ++m;printf("%d%s",i,m<n?" ":"
");
            }
        }
    }
    return 0;
}

 也可以使用优先队列：这里了解一下：priority_queue<Type, Container, Functional>Type为数据类型， Container为保存数据的容器，Functional为元素比较方式。如果不写后两个参数，那么容器默认用的是vector，比较方式默认用operator>，也就是优先队列是大顶堆，队头元素最大。

AC代码：注意输入输出要用C语言格式，不然真的会超时QAQ。。。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,x;
    priority_queue<int,vector<int>,greater<int> > q;
    while(~scanf("%d",&n)){
        while(n--){scanf("%d",&x);q.push(x);}
        while(q.size()>1){
            printf("%d ",q.top());q.pop();
        }
        printf("%d
",q.top());q.pop();
    }
    return 0;
}