題目：
某鐵路公司在建造火車站時，因當地居民的抗爭而無法取得足夠的土地建造足夠的鐵軌，因此他們建立了如下圖的一個特殊鐵軌站。火車固定由 A 方向進入，由 B 方向離開。而為了調度車廂，他們設了一個中介站 C 。車站軌道配置如下圖所示：
假設有 N 節車廂從 A 方向進入，按進站的次序，其編號分別為 1~N, N<=1000 。亦即，進入 A 站的車廂，其編號固定為 (1 ， 2 ， 3 ， ...， N) 。
你的任務是判斷能否讓這些車廂按照特定的編號次序離開 B 方向。例如（ 1 ， 2 ， 3 ， 4 ， 5 ）、（ 1 ， 5 ， 4 ， 3 ， 2 ）都是可行的離開次序；而（ 5 ， 4 ， 1 ， 2 ， 3 ）則不可行。
車廂一旦進入 C ，則不能再回到 A 。
輸入說明：
輸入包含同一種車廂長度的多筆測資。輸入的第 1 行指明車廂長度；接著的每一行均包含一種欲判斷的次序，每個數字之間以空白隔開。例如：
5
1 2 3 4 5
2 1 3 4 5
5 4 1 2 3
1 2 3 4 5
2 1 3 4 5
5 4 1 2 3
輸出說明 ：
針對每一行欲判斷的次序，逐行輸出是否可行。若是則輸出 ”YES” ；若否則輸出 ”NO”. 以上例而言，其輸出應為：
YES
YES
NO
YES
NO
#include <iostream>
#include <vector>
#include <stack>
// 自己瞎想的，單純把這題當堆疊模擬
// 可能有更好的演算法，但我不管，我就瞎寫，呵
using namespace std;
// 6
// 1 2 3 4 5 6 Y
// 4 3 2 5 1 6 Y
// 6 5 4 3 2 1 Y
// 1 4 2 5 3 6 N
// 6 5 4 1 2 3 N
// 1 2 3 6 5 4 Y
// c: <- / b: -^ / a: <-
// 重點：當B站持續發車到C軌，且給定表的下一班車編號與B站的頭列車編號對不上時 (而非單純是B站沒車了)，發車停止。
// 這裡的重點在於：
// 此時若(B站的頭列車編號 > 給定表的下一班車編號)，那麼這張表絕對有誤。
// 因為B站後面的火車無論如何一定要等前面的火車出去，而這是死局。
bool predicate(const vector<int> &c_trains)
{
stack<int> a_stack;
stack<int> b_stack;
for (int i = c_trains.size(); i > 0; i--)
a_stack.push(i);
for (int i = 0; i < c_trains.size();)
{
while ((a_stack.top() <= c_trains[i]))
{
b_stack.push(a_stack.top());
a_stack.pop();
if (a_stack.empty())
break;
}
while ((b_stack.top() == c_trains[i]))
{
i++;
b_stack.pop();
if (b_stack.empty())
break;
}
if (!b_stack.empty())
{
if ((b_stack.top() > c_trains[i]))
return false;
}
}
return true;
}
int main()
{
int n;
cin >> n;
vector<int> c_trains(n);
while (true)
{
for (int i = 0; i < n; i++)
{
cin >> c_trains[i];
if (c_trains[i] == -1)
goto end;
}
cout << (predicate(c_trains) ? "YES" : "NO") << endl;
}
end: return 0;
}
