題目： UVa - 514 - Rails

題目說明

給一個整數 n，代表有 1, 2, ..., n 個火車，每個火車入站可以直接出站或是等後面的火車入站並出站後再出站，簡單來講就是像 Stack 一樣。給一串數字代表火車出站的順序，若可以達成則輸出 "Yes" 否則輸出 "No"。

解題思路

使用 Stack 模擬火車入站出站，使用 Queue 儲存出站順序，若是 Stack 的 top() 與 Queue 的 front() 相同則兩者都不斷 pop()，直到兩者不相同或是 Stack 為空，結束後若 Stack 為空則表示這個順序是可行的。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <queue>
#include <stack>

using namespace std;

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

int main()
{
    int T, tmp;
    while (cin >> T && T)
    {
        while (cin >> tmp && tmp)
        {
            stack<int> s;
            queue<int> q;
            q.push(tmp);
            for (int i = 1; i < T; ++i) cin >> tmp, q.push(tmp);
            for (int i = 1; i <= T; ++i)
            {
                s.push(i);
                while (!s.empty() && s.top() == q.front()) s.pop(), q.pop();
            }
            cout << (s.empty() ? "Yes\n" : "No\n");
        }
        cout << '\n';
    }
}