车厢调度

车厢调度
运行时限: 10000 ms 单次运行时限: 10000 ms 内存限制: 2047 MB
总提交: 5次 通过: 1次

题目描述

有一个火车站，铁路如图所示，每辆火车从 A 驶入，在从 B 方向驶出，同时它的车厢可以重新组合。假设从 A 方向驶来的火车有 n 节（n <=1000），分别按照顺序编号为1、2、3、…、n。假设在进入车站前，每节车厢之间都不是连着的，并且它们可以自行移动到 B 处的铁轨上。另外假定车站 C 可以停放任意多节车厢。但是一旦进入车站 C， 它就不能在回到 A 方向的铁轨上了，并且一旦它进入 B 方向的铁轨，它就不能回到车站C。

负责车厢调度的工作人员需要知道能否使它以 a1、a2、…、an的顺序从 B 方向驶出，请判断能否得到指定的车厢顺序。

程序输入说明

输入文件的第一行为一个整数 n ，其中 n < = 1000，表示有 n 节车厢，第二行为 n 个数字，表示指定的车厢顺序。

程序输出说明

如果可以得到指定的车厢顺序，则输出一个字符串“YES” ，否则输出 “NO”（注意要大写，不包含引号）。

程序输入样例

可见格式 带空格和换行符的格式 带空格和换行符的格式说明

5
5 4 3 2 1 

程序输出样例
Original Transformed 带空格和换行符的格式说明

YES

其实就是给你一个序列,让你判断是否为正确出栈顺序,进栈顺序为1,2,3,4,5

#include <stdlib.h>
#include <stdio.h>

int n,stack[1010];

int main()
{
    int i,j,max,c,top;
    scanf("%d",&n);
    max=0;
    top=0;
    c=0;
    for(i=1; i<=n; i++)
    {
        scanf("%d",&c);
        if(c>max) //当前元素大于栈中最大的元素，则比此元素小的元素都入栈
        {
            for(j=max+1; j<=c; j++)
                stack[++top] = j;
            max = c;
        }
        if(c<=max) //当前元素小于等于栈中最大元素，判断栈顶元素是否等于该元素
        {
            if(c == stack[top])
                top--;
            else
            {
                printf("NO\n");
                return 0;
            }
        }
    }
    printf("YES\n");
    return 0;
}

STL

#include <iostream>
#include <stack>
#include <cstdio>
using namespace std;
const int MAXN = 1000 + 100;

int n,target[MAXN];

int main()
{
    while(scanf("%d",&n)==1)
    {
        stack<int> s;
        int A = 1,B = 1;
        for(int i=1;i<=n;i++)
            scanf("%d",&target[i]);
        int ok = 1;
        while(B<=n)
        {
            if(A==target[B])
            {
                A++;
                B++;
            }
            else if(!s.empty() && s.top() == target[B])
            {
                s.pop();
                B++;
            }
            else if(A<=n)
                s.push(A++);
            else
            {
                ok = 0;
                break;
            }

        }
        printf("%s\n",ok ? "YES":"NO");
    }
    return 0;
}