d166: 反轉表

內容

由 1 開始之連續數字 a1.a2.a3…an 相對有一反轉表：b1.b2…bm。其 bm 代表意思為：數字 m 的位置前面有幾個比大個個數。

2 3 6 4 0 2 2 1 0
第 1 個 2 為 1 前面有 2 個比它大的數
第 2 個 3 為 2 前面有 3 個比它大的數
第 3 個 6 為 3 前面有 6 個比它大的數….以此類推
所以答案為
5 9 1 8 2 6 4 7 3
數字 1 前面有 2 個比它大的數 5 9
數字 2 前面有 3 個比它大的數 5 9 8

輸入

輸入的每一行含有一個由 m 個數所組成的數列(反轉表) 1<=m<=50，

單獨一個 -1 在一行代表測試資料的結束

2 3 6 4 0 2 2 1 0

-1

輸出

請輸出從 1 到 m 所代表的數列

5 9 1 8 2 6 4 7 3

解題思路

從小到大將項目數新增至陣列，並在前面保留輸入值個元素讓後面更大的元素可以放進去。

以測資為範例

1. [輸入] 2 3 6 4 0 2 2 1 0
   [答案] 0 0 1 0 0 0 0 0 0

2. [輸入] 2 3 6 4 0 2 2 1 0
   [答案] 0 0 1 0 2 0 0 0 0

3. [輸入] 2 3 6 4 0 2 2 1 0
   [答案] 0 0 1 0 2 0 0 0 3

4. [輸入] 2 3 6 4 0 2 2 1 0
   [答案] 0 0 1 0 2 0 4 0 3

5. [輸入] 2 3 6 4 0 2 2 1 0
   [答案] 5 0 1 0 2 0 4 0 3

6. [輸入] 2 3 6 4 0 2 2 1 0
   [答案] 5 0 1 0 2 6 4 0 3

7. [輸入] 2 3 6 4 0 2 2 1 0
   [答案] 5 0 1 0 2 6 4 7 3

8. [輸入] 2 3 6 4 0 2 2 1 0
   [答案] 5 0 1 8 2 6 4 7 3

9. [輸入] 2 3 6 4 0 2 2 1 0
   [答案] 5 9 1 8 2 6 4 7 3

完整程式碼

AC (2ms, 108KB)

#include <stdio.h>
#define MAX 55

char input[10000];

inline char* getUInt(unsigned int* dst, char src[])
{
    while (*src < '0')
        if (!*src++) return NULL;
    *dst = *src ^ '0';
    while (*++src >= '0')
        * dst = (*dst << 3) + (*dst << 1) + (*src ^ '0');
    return src;
}

int main()
{
    while (gets(input) && input[0] != '-')
    {
        char* st = input;
        int ans[MAX] = { 0 }, tmp, j;
        for (int i = 0; st = getUInt(&tmp, st); i++)
        {
            for (j = 0; tmp || ans[j]; j++)
                if (!ans[j]) tmp--;
            ans[j] = i + 1;
        }
        for (int i = 0; ans[i]; i++)
            printf("%d ", ans[i]);
        putchar('\n');
    }
    return 0;
}