d587: 參貳壹真好吃

2019-09-02

內容

參貳壹真是太好吃了！
現在有一連串由 1、2、3 這三個數字組成的數列，
請你把他們由小到大排好好嗎？

輸入

本題有 2 個測資點，每個 50 分，每個測資點只有一組測資。
第一行有整數 n(1<=n<=1000000)代表接下來的數列有幾個數字
第二行就是這 n 個包含 1、2、3 的數字

9
1 1 1 2 2 3 3 3 2

輸出

對於每組測資，請輸出一行由小到大 1~3 排好的結果。

1 1 1 2 2 2 3 3 3

解題思路

簡單的基數排序，由於輸出只有 1, 2, 3 三種可能所以建好表直接用 fputs()輸出字串節省 printf()的運算時間。

完整程式碼

AC (3ms, 116KB)

#include <stdio.h>

int list[4];
char outstr[4][3] = { "", "1 ", "2 " , "3 " };

int main()
{
    int n, tmp;
    scanf(" %d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf(" %d", &tmp);
        list[tmp]++;
    }
    for (int i = 1; i <= 3; i++)
    {
        while (list[i]--)
            fputs(outstr[i], stdout);
    }
    return 0;
}