alan23273850 的刷題筆記
c123: 00514 - Rails
Tags: stack
出處：https://zerojudge.tw/ShowProblem?problemid=c123
提交：https://zerojudge.tw/Submissions?problemid=c123&account=allllllan123456
問題：給定一組 1 到 $N\in[1,1000]$ 的任意排列來描述 B 軌道 (只進不出) 的停車狀態，請問有沒有辦法從一開始已先按照遞增順序排好的 A (只出不進) 透過中間的 stack 來達成？
解法：這題就蠻經典的資料結構題目，因為題目限制的不可逆性，所以只能從 B 的左邊開始一個一個去 match。每次我只能先 match 中間 station 的 top 是不是 B 接下來所期望的 (right) top，是的話就把它從 station 抓出來並推進 B，不是的話就把 A 的 (left) top 抓進 station 並重複前述動作直到結束。如果最後沒辦法 match 完畢，也就是當 A 已經 empty 的時候中間的 station 還留有冗餘元素，這樣就是失敗，否則目標便已經達成。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
5 int N;
6 while (cin >> N && N) { int t;
7 while (cin >> t && t) {
8 int N2 = N-1; stack<int> s;
9 for (int i=1; i<=N; i++) {
10 s.push(i);
11 while (s.size() && s.top()==t) {
12 s.pop();
13 if (N2) cin >> t, N2--;
14 }
15 }
16 cout << (!N2 ? "Yes\n" : "No\n");
17 while (N2--) cin >> t;
18 }
19 cout << '\n';
20 }
21 return 0;
22}