ZeroJudge 解題筆記：d166. 反轉表

作者：王一哲
日期：2025年8月24日


ZeroJudge 題目連結：d166. 反轉表

解題想法

實際上有多筆測資，讀取到 EOF 才停止，如果整行只有一個 -1 要 continue 不能 break。 倒著往回讀資料，像是範例中的資料為

2 3 6 4 0 2 2 1 0

共有 9 個數字，代表 1 ~ 9 前面各有幾個數字比自己還大，因為最後一位是 9，前面不可能有比 9 大的數，因此資料中這格一定是 0，先將 9 放到儲存答案的陣列之中。

9

倒數第 2 位代表 8，前面有 1 位比 8 大的數字，代表 8 放在 9 後面，因此陣列為

9 8

倒數第 3 位代表 7，前面有 2 位比 7 大的數字，代表 7 放在最後面，因此陣列為

9 8 7

倒數第 4 位代表 6，前面有 2 位比 6 大的數字，代表 6 放在 7、8 之間，因此陣列為

9 8 6 7

倒數第 5 位代表 5，前面沒有比 5 大的數字，代表 5 放最前面，因此陣列為

5 9 8 6 7

我們可以看出，位數對應的值代表這個位數要插入陣列中的索引值，依照這個方式寫程式碼即可。

Python 程式碼

使用時間約為 19 ms，記憶體約為 3.3 MB，通過測試。

import sys

for line in sys.stdin:
    rev = tuple(map(int, line.split()))  # 反轉表
    n = len(rev)  # n 個數字
    if n == 1 and rev[0] == -1: continue  # 如果整行只有 -1，讀下一筆
    arr = []  # 輸出答案用的串列
    for i in range(n, 0, -1):  # 倒著讀反轉表
        arr.insert(rev[i-1], i)  # 依照反轉表的值將位數插入 arr 之中
    print(*arr)  # 印出 arr

C++ 程式碼

使用時間約為 2 ms，記憶體約為 352 MB，通過測試。

#include <iostream>
#include <vector>
#include <sstream>
using namespace std;

int main () {
    ios::sync_with_stdio(0); cin.tie(0);
    string s;  // 暫存整行資料用的字串
    stringstream ss;  // 暫存資料用的容器
    vector<int> rev, arr;  // 反轉表，答案
    while(getline(cin, s)) {  // 讀取整行資料直到 EOF 為止
        ss.clear(); ss << s;  // 清空 ss 再存入 s 的資料
        rev.clear();  // 清空 rev
        while(ss >> s) rev.push_back(stoi(s));  // 從 ss 讀取資料存入反轉表
        int n = (int)rev.size();  // n 個數字
        if (n == 1 && rev[0] == -1) continue;  // 如果整行只有 -1，讀下一筆
        arr.clear();  // 清空 arr
        for(int i=n; i>=1; i--) {  // 倒著讀反轉表
            arr.insert(arr.begin()+rev[i-1], i);  // 依照反轉表的值將位數插入 arr 之中
        }
        for(int i=0; i<n; i++) {  // 印出 arr
            cout << arr[i] << " \n"[i == n-1];
        }
    }
    return 0;
}