SSL 2311-车厢调度[栈]

Description

在PushPop城中有一个著名的火车站，车站铁路如图所示。
这里写图片描述
每辆火车都从A方向驶入车站，再从B方向驶出车站，同时它的车厢可以进行某种形式的重新组合。假设从A方向驶来的火车有N节车厢（N≤1000），分别按顺序编号为1，2，…，N。负责车厢调度的工作人员需要知道能否使它以A1，A2，…，An的顺序从B方向驶出。
请你编写程序，用来判断能否得到指定的车厢顺序。假定在进入车站之前每节车厢之间都是不连着的，并且它们可以自行移动，直到处在B方向的铁轨上。另外假定车站可以停放任意多的车厢。但是一旦车厢进入车站，它就不能再回到A方向的铁轨上了，并且一旦它驶入B方向的铁轨后，它就不能再回到车站。

Input

第1行输入N，接下来的一行是任意多个的出站重组顺序（A1，A2，…，），以0为结束标志，用空格分隔。

Output

输出Yes表示可以把火车（1，2，…，N）火车编排成所需要的顺序（A1，A2，…，），否则用NO表示。

Sample Input

5
5 4 3 2 1

Sample Output

YES

.
.
.
.
.

分析

在中转站C中，车厢符合后进先出的原则，因此是一个栈。

假设我们已经处理了前i-1节从B方向驶出的车厢，我们现在要让 $a_{i}$ 驶出。

若 $a_{i}$ 不在车站C中，我们就让若干车厢从A方向驶入车站C，直到 $a_{i}$ 驶入，再将它从B方向驶出；

若 $a_{i}$ 在车站C中，如果它是车站C中停在最前面的，则将它从B方向驶出，否则原问题误解。
.
.
.
.
.

程序：

#include<iostream>
using namespace std;
int main()
{
    int n,stack[2000],a[2000];
    cin>>n;
    for (int i=1;i<=n;i++)
    cin>>a[i];
    int top=0,bh=1;
    for (int i=1;i<=n;i++)
    {
        while (bh<=a[i])
        {
            stack[++top]=bh;
            bh++;
        }
        if (stack[top]==a[i]) top--;
        else
        {
            cout<<"NO";
            return 0;
        }
    }
    cout<<"YES";
    return 0;
}