第 16 周作業講解

第 16 周作業講解
- 957 - 火車觀景台

957 - 火車觀景台

解題思路

根據題目敘述，可以發現山洞可以抽象成 queue，而轉運站則是 stack。我們可以直接模擬火車的行為，並看模擬的過程中有沒有發現不可行的地方就知道有沒有火車出軌。為了方便，我們把 B 山洞視為一個門，也就是火車會直接通過，而不像 A 山洞可以停火車在裡面，如此就不需要用一個容器來模擬 B 山洞，同時維持正確性。
我們需要模擬：

觀察到 A 山洞有火車進去
觀察到 B 山洞有火車出來

要模擬觀察到有火車從 A 進去其實不難，把數字放入 queue 即可。
觀察到有火車從山洞 B 出來，該火車本來的位置有兩種可能：

火車在轉運站（stack 的頂）
火車在 A 山洞

火車如果在轉運站，就直接 pop 出來就可以；如果不在轉運站，那我們就要檢查他是不是在 A 山洞裡面，且根據規則，火車要先開進轉運站才能出來，所以我們可以不斷檢查 A 山洞這個 queue 的頭，如果不是我們要的火車，就把他停進轉運站中，直到找到我們要的火車，並且停到轉運站後開出來。最後，如果以上兩個情況都不符合，就代表火車出軌了。

程式框架

使用一個 stack 表示轉運站，一個 queue 表示 A 山洞。並且建立一個標籤，用來標記過程中有沒有問題，觀察到出軌的話，這個標籤就會變成 false。

stack<int> s;
queue<int> A;
bool good = true;

對於每個事件，我們接收一個字元和整數：

char op;
int x;
cin >> op >> x;

如果字元是 A，代表火車進入山洞 A，因此就直接將收到的號碼放入 queue 中即可：

A.emplace(x);

否則，觀察到 B 山洞有火車出來，我們先考慮火車不在轉運站中的情況，也就是轉運站是空的，或是轉運站最外面的火車不是我們要的：

if (s.empty() || s.top() != x) {
    // 把不是我們要的火車停到轉運站中
    while (!A.empty() && A.front() != x) {
        int ft = A.front();
        A.pop();
        s.emplace(ft);
    }
    
    // 所有火車都不是我們要的，也就找不到觀察到的火車，代表出軌了。
    if (A.empty()) {
        good = false;
        break;
    }
    
    // 剩下在 A.front() 的火車就是我們要的，直接把他開出來。
    A.pop();
}

當 A.front() 是我們要的火車時，我們本來應該一樣要把他停到轉運站中再開出來，如下面這樣，但是放到轉運站又拿出來的動作多此一舉，因此可以直接省去

int ft = A.front();
A.pop();
s.emplace(ft);
s.pop()

排除以上可能後，火車在就在轉運站的最外面，直接開出來即可：

s.pop();

輸入迴圈結束時，利用之前的標誌，可以知道有沒有出軌：

if (good) {
    cout << "Good";
} else {
    cout << "Ooops!!!";
}

其他注意事項

這題因為輸入很多的關係，程式可能會被 cin 拖住導致 TLE，建議同學可以加入下面的輸入輸出優化來避免以上情況發生：

ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

完整程式碼


















































#include <iostream>
#include <queue>
#include <stack>
using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin >> n;

    stack<int> s;
    queue<int> A;
    bool good = true;

    while (n--) {
        char op;
        int x;
        cin >> op >> x;
        if (op == 'A') {
            A.emplace(x);
        } else {
            if (s.empty() || s.top() != x) {
                while (!A.empty() && A.front() != x) {
                    int ft = A.front();
                    A.pop();
                    s.emplace(ft);
                }

                if (A.empty()) {
                    good = false;
                    break;
                }

                A.pop();
            } else {
                s.pop();
            }
        }
    }

    if (good) {
        cout << "Good";
    } else {
        cout << "Ooops!!!";
    }
}