鐵軌
PopPush城市有一座著名的火車站。這個國家到處都是丘陵。而這個火車站是建于上一個世紀。不幸的是，那時的資金有限。所以只能建立起一條路面鐵軌。而且，這導致這個火車站在同一個時刻只能一個軌道投入使用，因為它缺少空間，兩列火車將無路可走。具體看下圖。
當地的慣例是每一列火車從A方向駛向B方向時候，會用某種方式將車廂重組。假設火車將要到達A方向，擁有N個車廂(N<=1000),這些車廂按照遞增順序標記為1到N。負責從組車廂的領導,必須知道是否能從組車廂讓它駛出B，而這個重組的序列就是a1\a2\a3...aN.幫組他并且寫一個程序來判斷是否可能按照所要求的車廂順序。你可以假設，單個的車廂可以從列車上分離出來，在他們進入站臺之前。并且他們可以自由移動，知道它們上了B軌道。你也可以假設在任意時候站臺可以放下無數的車廂。但是只要一個車廂進入站臺，它就不能返回A軌道，同時如果它離開了站臺駛向B軌道，它就不能返回站臺。
輸入：
這個輸入文件由多個行塊組成。每一個塊描述的是多個要求的重組車廂的序列。在這每個塊中的第一行是一個整數N，被用來說明上面每行的車廂個數。這個快的最后一行僅僅是一個數字0要來標記該快的結束
最后一個塊僅僅是一個0獨占一行。
輸出：
這個輸出文件包含多行，這些行和排列車廂的行數一一對應。日過該排列可行，則輸出Yes，否則輸出No。另外存在一個空行在每個相對應的塊后面。輸出文件中不存在于最后一個什么數據都沒有的響應輸出。
輸出
5
1 2 3 4 5
5 4 1 2 3
0
6
6 5 4 3 2 1
0
0
Output
Yes
No
Yes
1 /*
2 由于station符合后進先出規則，所以可以用一個stack<int>來表示station。
3 然后采用模擬的規則來寫，因為進入station是按照編號遞增進入，所以可以用aId變量表示。
4 接下來就是模擬時候應該注意的條件，我們知道有以下兩種情況，一種是一進來station，就出station
5 也就是 aId == coaches[lenB]; 一種是進來時還不出站，那么這時候就要s.push(aId),但是這一種的條件呢？
6 我們如果可以排除掉第一種，那么無非就是第二種了。但是我們要知道，在進站之前，如果站臺里有車它是可以先出站的
7 ，這種狀態就條件就是 !s.empty() && s.top() == coaches[lenB].所以只要按照順序判斷這幾個條件
8 就可以寫出這個模擬程序了。
9
10
11 總結：
12 解決問題的關鍵點，在于構建問題的模型、大部分都是可以用現有的基礎數據結構。構造完對應的數據結構，特別是對于模擬題
13 無非就是狀態見的轉移處理，這是就要在基于模型的基礎上、先寫出映射到個個狀態的唯一條件，然后按照問題邏輯一一先后判斷
14 即可。
15 */
16 #include <iostream>
17 #include <stack>
18
19 using namespace std;
20 const int len = 1024;
21 int coaches[len];
22
23 int main() {
24
25 int n;
26 while (cin >> n, n) {
27 stack<int> s;
28 // read the required permutaion
29
30 while ( cin >> coaches[0], coaches[0]) {
31
32 for (int i = 1; i < n; i++) {
33 cin >> coaches[i];
34 }
35 int lenB = 0, aId = 1;
36 bool ok = true;
37 while (lenB < n) {
38
39 if (aId == coaches[lenB]) { aId++; lenB++; }
40 else if(!s.empty() && s.top() == coaches[lenB]) { s.pop(); lenB++; }
41 else if(aId <= n) s.push(aId++);
42 else { ok = false; break; }
43
44 }
45
46 cout << (ok ? "Yes" : "No") << endl;
47 }
48 cout << endl;
49 }
50
51 return 0;
52 }
2015/3/30下午3:03:52