# 題目: UVa 514 - Rails
# 題目說明
有一個火車站,出去及進來都只有一條路
有一對列按照編號順序排列的火車
它們是否能按照特定順序出車站?
INPUT:
每筆資料的第一行有一個整數 n
,代表有 n
個火車
接著有 n
個整數,代表火車出站的順序
當第一個順序為 0
時,結束這筆資料
當 n
為 0
時,結束程式
OUTPUT:
當順序為可行時,輸出 Yes
,否則輸出 No
# 解題方法
用 stack a
儲存資料,按照順序找到火車 (判斷 stack a
及 stack b
的 top
)
並將這台火車前面的火車都 push
到 stack b
如果過程中 stack a
變為空,則不可行
# 參考程式碼
#include <iostream> | |
#include <stack> | |
using namespace std; | |
int main() | |
{ | |
ios::sync_with_stdio(false); | |
cin.tie(nullptr); | |
cout.tie(nullptr); | |
int n, in; | |
while (cin >> n && n) { | |
while (cin >> in && in) { | |
bool success = true; | |
stack<int> A, station; | |
for (int i = n; i > 0; --i) A.emplace(i); | |
for (int i = 0; i < n; ++i) { | |
if (i) cin >> in; | |
if (!station.empty() && station.top() == in) station.pop(); | |
else { | |
while (!A.empty() && A.top() != in) station.emplace(A.top()), A.pop(); | |
if (A.empty()) success = false; | |
else A.pop(); | |
} | |
} | |
cout << (success ? "Yes\n" : "No\n"); | |
} | |
cout << "\n"; | |
} | |
return 0; | |
} |
# 參考資料
https://www.larrysprognotes.com/UVa%20-%20514/