sicily 1509 Rails 解题总结

summary

:

这题很明显，可以用2个栈来模拟，车进去是一个栈s，然后相当于有一个让道（可以看作 一个栈ss），储存先不出去的车厢。读取输入的车的顺序，放进数组里面，然后s先初始化 一个完整的栈n......2，1。对于输出的车的顺序的每一个元素，先检查的栈顶元素是否与它相 同，再检查ss的栈顶元素是否与它相同，如果都不相同，则s的栈顶元素出栈，继续找下一 元素，如果都找不到，则该顺序不可能产生。

代码:

#include <iostream>
#include <stack>

using namespace std;

const int N = 1001;

int main()
{
    unsigned n,a[N];
    unsigned i;

    while(cin >> n && n){
        while(cin >> a[0] && a[0]){
            for(i = 1; i < n; i++){
                cin >> a[i];
            }
            stack<int> s;
            stack<int> ss;
            for(i = n; i > 0; i--){
                s.push(i);
            }
            for(i = 0; i < n; i++){
                if(!s.empty() && s.top() == a[i]){
                    s.pop();
                }else if(!ss.empty() && ss.top() == a[i]){
                    ss.pop();
                }else if(!s.empty() && s.top() != a[i]){
                    while(!s.empty() && s.top() != a[i]){
                        ss.push(s.top());
                        s.pop();
                    }
                    if(!s.empty())
                        s.pop();
                    else
                        break;
                }else{
                    break;
                }
            }
            if(i == n){
                cout << "Yes" << endl;
            }else{
                cout << "No" << endl;
            }
        }
        cout << endl;
    }
    return 0;
}