andyli

题解 UVA11462 【Age Sort】
由于数据量太大,这里不建议使用快排函数。这里可以利用整数范围很小这个条件来使用计数排序方法。下面是程序代码:#in...
扫描右侧二维码阅读全文
13
2018/05

题解 UVA11462 【Age Sort】

由于数据量太大,这里不建议使用快排函数。这里可以利用整数范围很小这个条件来使用计数排序方法。下面是程序代码:

#include <cstring>
#include <cstdio>
using namespace std;

int main()
{
    int n, x, c[101];
    while (scanf("%d", &n) == 1 && n)
    {
        memset(c, 0, sizeof(c));
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &x);
            c[x]++;
        }
        int first = 1;
        for(int i = 1; i <= 100; i++)
            for (int j = 0; j < c[i]; j++)
            {
                if (!first) printf(" ");
                first = 0;
                printf("%d", i);
            }
        printf("\n");
    }
    return 0;
}

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

#include <cstring>
#include <cstdio>
#include <cctype>

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;
    if (i == 0)
        p++; // 特殊情况:i等于0时需要输出0,而不是什么也不输出
    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, 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');
    }
    return 0;
}

上述优化使得运行时间缩短了约2/3。一般情况下,当输入输出数据量很大时,应尽量用scanf和printf函数(而不是cin和cout);如果时间效率还不够高,应逐字符输入输出,就像上面的readint和writeint函数。

Last modification:June 25th, 2019 at 11:01 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment