鐵軌
PopPush城市有一座著名的火車站。這個(gè)國(guó)家到處都是丘陵。而這個(gè)火車站是建于上一個(gè)世紀(jì)。不幸的是，那時(shí)的資金有限。所以只能建立起一條路面鐵軌。而且，這導(dǎo)致這個(gè)火車站在同一個(gè)時(shí)刻只能一個(gè)軌道投入使用，因?yàn)樗鄙倏臻g，兩列火車將無(wú)路可走。具體看下圖。
當(dāng)?shù)氐膽T例是每一列火車從A方向駛向B方向時(shí)候，會(huì)用某種方式將車廂重組。假設(shè)火車將要到達(dá)A方向，擁有N個(gè)車廂(N<=1000),這些車廂按照遞增順序標(biāo)記為1到N。負(fù)責(zé)從組車廂的領(lǐng)導(dǎo),必須知道是否能從組車廂讓它駛出B，而這個(gè)重組的序列就是a1\a2\a3...aN.幫組他并且寫一個(gè)程序來(lái)判斷是否可能按照所要求的車廂順序。你可以假設(shè)，單個(gè)的車廂可以從列車上分離出來(lái)，在他們進(jìn)入站臺(tái)之前。并且他們可以自由移動(dòng)，知道它們上了B軌道。你也可以假設(shè)在任意時(shí)候站臺(tái)可以放下無(wú)數(shù)的車廂。但是只要一個(gè)車廂進(jìn)入站臺(tái)，它就不能返回A軌道，同時(shí)如果它離開(kāi)了站臺(tái)駛向B軌道，它就不能返回站臺(tái)。
輸入：
這個(gè)輸入文件由多個(gè)行塊組成。每一個(gè)塊描述的是多個(gè)要求的重組車廂的序列。在這每個(gè)塊中的第一行是一個(gè)整數(shù)N，被用來(lái)說(shuō)明上面每行的車廂個(gè)數(shù)。這個(gè)快的最后一行僅僅是一個(gè)數(shù)字0要來(lái)標(biāo)記該快的結(jié)束
最后一個(gè)塊僅僅是一個(gè)0獨(dú)占一行。
輸出：
這個(gè)輸出文件包含多行，這些行和排列車廂的行數(shù)一一對(duì)應(yīng)。日過(guò)該排列可行，則輸出Yes，否則輸出No。另外存在一個(gè)空行在每個(gè)相對(duì)應(yīng)的塊后面。輸出文件中不存在于最后一個(gè)什么數(shù)據(jù)都沒(méi)有的響應(yīng)輸出。
輸出
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符合后進(jìn)先出規(guī)則，所以可以用一個(gè)stack<int>來(lái)表示station。
3 然后采用模擬的規(guī)則來(lái)寫，因?yàn)檫M(jìn)入station是按照編號(hào)遞增進(jìn)入，所以可以用aId變量表示。
4 接下來(lái)就是模擬時(shí)候應(yīng)該注意的條件，我們知道有以下兩種情況，一種是一進(jìn)來(lái)station，就出station
5 也就是 aId == coaches[lenB]; 一種是進(jìn)來(lái)時(shí)還不出站，那么這時(shí)候就要s.push(aId),但是這一種的條件呢？
6 我們?nèi)绻梢耘懦舻谝环N，那么無(wú)非就是第二種了。但是我們要知道，在進(jìn)站之前，如果站臺(tái)里有車它是可以先出站的
7 ，這種狀態(tài)就條件就是 !s.empty() && s.top() == coaches[lenB].所以只要按照順序判斷這幾個(gè)條件
8 就可以寫出這個(gè)模擬程序了。
9
10
11 總結(jié)：
12 解決問(wèn)題的關(guān)鍵點(diǎn)，在于構(gòu)建問(wèn)題的模型、大部分都是可以用現(xiàn)有的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)。構(gòu)造完對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)，特別是對(duì)于模擬題
13 無(wú)非就是狀態(tài)見(jiàn)的轉(zhuǎn)移處理，這是就要在基于模型的基礎(chǔ)上、先寫出映射到個(gè)個(gè)狀態(tài)的唯一條件，然后按照問(wèn)題邏輯一一先后判斷
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