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 integern(0<n<=2000000), the total number of people. In the next line, there arenintegers indicating the ages. Input is terminated with a case wheren= 0. This case should not be processed.

Output

For each case, print a line withnspace 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 InputOutput 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');
    }//while
    return 0;
}

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