POJ 1363 Rails - 棧模擬判斷火車調度可行性

問題描述

有一個死端側線（棧），入口方向 A 進入 N 節車廂（編號 1..N），出口方向 B 需要按給定排列順序重組。車廂只能從 A 進入側線，或從側線移出到 B，不能倒退。判斷給定的目標排列是否可行。

棧模擬算法

維護一個棧 stk 模擬側線，指針 nextIn = 1 表示下一個進站車廂，nextOut = 0 表示目標排列當前位置。重複：若棧頂等於目標 target[nextOut]，出棧並 nextOut++；否則若 nextIn ≤ N，將 nextIn 入棧並 nextIn++；否則無法繼續，失敗。若最終 nextOut == N 則成功。

輸入輸出細節

• 輸入包含多組測試塊，每塊第一行 N，其後多行目標排列，以 0 結束塊；最後一塊單獨一個 0 結束輸入。
• 每塊輸出對應每行排列的 "Yes"/"No"，塊之間空一行。

複雜度

每排列 O(N) 時間，O(N) 空間，N ≤ 1000 完全足夠。

參考代碼 (C++)

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

int main() {
    int N;
    while (scanf("%d", &N) == 1 && N) {
        while (true) {
            int target[1005];
            scanf("%d", &target[0]);
            if (target[0] == 0) break;
            for (int i = 1; i < N; ++i) scanf("%d", &target[i]);

            stack<int> stk;
            int nextIn = 1, nextOut = 0;
            while (nextOut < N) {
                if (!stk.empty() && stk.top() == target[nextOut]) {
                    stk.pop();
                    ++nextOut;
                } else if (nextIn <= N) {
                    stk.push(nextIn++);
                } else break;
            }
            puts(nextOut == N ? "Yes" : "No");
        }
        puts("");
    }
    return 0;
}