POJ-1363 Rails (模拟+栈）

http://poj.org/problem?id=1363

题意：

n个火车按序排列，1，2，3...,n，然后任意给出一组序列，问火车通过人字轨道是否可以生成这组序列。人字轨道从A端进，B端出。

第一行输入火车列数，接下来输出生成的火车编号，出入0表示这组案例结束。最后输出能否生成该编号序列。

思路：

模拟栈 的生成及弹出过程即可的出答案。

代码：

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string>
#include<iomanip>
#include<algorithm>
#include<string.h>
#include<queue>
#include<cmath>

using namespace std;
const int maxn=1e5+10;
const int inf=1e10;
typedef long long ll;

int a[maxn],b[maxn],sk[maxn];

int main()
{
    int n;
    int top;
    while(cin>>n&&n)
    {
        memset(sk,0,sizeof(sk));
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for(int i=0; i<n; i++) a[i]=i+1;
        int i;
        while(cin>>b[0]&&b[0])
        {
            for(i=1; i<n; i++) cin>>b[i];
            top=0;
            int j=1;
            for(i=0; i<n&&j<=n+1; )
            {
                if(j==b[i])//若当前火车标号和当前i位置标号一致，则继续匹配
                {
                    j++;
                    i++;
                }
                else if(top&&sk[top-1]==b[i])//否则和栈顶元素进行匹配
                {
                    top--;
                    i++;
                }
                else //都不匹配，则入栈
                {
                    sk[top++]=j++;
                }
            } 
            if(i==n) cout<<"Yes"<<endl;//n个元素全部匹配完毕
            else cout<<"No"<<endl;
        }
        cout<<endl;

    }

    system("pause");
    return 0;
}