原題如下
1001. Rails
Time Limit: 1sec Memory Limit:32MB
Description
There is a famous railway station in PopPush City. Country there is incredibly hilly. The station was built in last century. Unfortunately, funds were extremely limited that time. It was possible to establish only a surface track. Moreover, it turned out that the station could be only a dead-end one (see picture) and due to lack of available space it could have only one track.
The local tradition is that every train arriving from the direction A continues in the direction B with coaches reorganized in some way. Assume that the train arriving from the direction A has N <= 1000 coaches numbered in increasing order 1, 2, …, N. The chief for train reorganizations must know whether it is possible to marshal coaches continuing in the direction B so that their order will be a1, a2, …, aN. Help him and write a program that decides whether it is possible to get the required order of coaches. You can assume that single coaches can be disconnected from the train before they enter the station and that they can move themselves until they are on the track in the direction B. You can also suppose that at any time there can be located as many coaches as necessary in the station. But once a coach has entered the station it cannot return to the track in the direction A and also once it has left the station in the direction B it cannot return back to the station.
Input
The input consists of blocks of lines. Each block except the last describes one train and possibly more requirements for its reorganization. In the first line of the block there is the integer N described above. In each of the next lines of the block there is a permutation of 1, 2, …, N. The last line of the block contains just 0.
The last block consists of just one line containing 0.
Output
The output contains the lines corresponding to the lines with permutations in the input. A line of the output contains Yes if it is possible to marshal the coaches in the order required on the corresponding line of the input. Otherwise it contains No. In addition, there is one empty line after the lines corresponding to one block of the input. There is no line in the output corresponding to the last ``null’’ block of the input.
Sample Input Copy
5
1 2 3 4 5
5 4 1 2 3
0
6
6 5 4 3 2 1
0
0 複制
Sample Output Copy
Yes
No
Yes 複制
思路
簡單點說就是車廂從右邊過來，進入Station，并且必須排隊出來，也就是說，如果有幾個車廂在站内，則後進的車廂先出站。
這後進先出正好符合棧的特點，可以考慮使用棧解決。
要判斷一個序列是否有可能，隻需要看是否能夠找到一個進站出站的方案滿足這個序列，即隻需要測試是否能夠由輸入的序列經過入棧出棧的操作，得到該結果序列。
将待判斷的結果序列放到一個vector中（相當于數組），将站内停靠的序号放到stack中。
(1) 當站内為空時，則必須入棧，此時如果棧頂與序列的第一個數相同時，則出棧，并将vector一個元素删去，表示已比對；
(2) 若不比對，則繼續入棧，直到比對為止，當出棧時還必須考慮出棧之後的棧頂是不是能夠跟vector的一個元素比對。
(3) 重複(1)(2)的操作。如果最終vector的元素為空，即是以的元素都能被比對上，則說明這個序列是可能的。如果所有車廂号都已經入棧了，且棧頂無法與vector比對，且vector還沒被比對完，則說明此序列不可能，因為找不到一個方案可以得出這個序列。
代碼
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main(){
int n;
cin >> n;
while(n > 0){
int a;
cin >> a;
if(a == 0) {
cout << endl;
cin >> n;
continue;
}
vector<int> num;
num.push_back(a);
for(int i = 1; i < n; i++){
int input;
cin >> input;
num.push_back(input);
}
int cur = 1;
stack<int> s;
/*******以下為關鍵代碼********/
while(!num.empty()){
if(cur > n){
cout << "No" << endl;
break;
}
s.push(cur);
cur += 1;
while(!s.empty() && s.top() == num.front()){
s.pop();
num.erase(num.begin());
}
}
if(num.empty()) cout << "Yes" << endl;
}
} 複制