14161: 【原4161】Rails

题目

题目描述

author: DS TA 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4161

Description

某城市有一个火车站，有n节车厢从A口驶入车站，按进站顺序编号为1~n，车厢顺序经过调整后，从B口驶离车站。

为了重组车厢，你可以借助中转站C。这是一个可以停放任意多节车厢的车站，但由于末端封顶，驶入C的车厢必须按相反的顺序驶离C。

对于每个车厢，一旦从A驶入C，就不能再回到A；一旦从C驶入B，就不能回到C了。换句话说，在任意时刻，只有两种选择：A->C和C->B。

你的任务是，判断能否让n节车厢按照某种特定的顺序从B口驶离车站。

Input Format

输入包括两行

第一行包括一个整数n(1<=n<=100)。代表驶入车站的车厢数量。

第二行包括从1到n的n个整数组成的序列，代表车厢驶离车站的顺序，整数之间以空格分开。

Output Format

如果车厢可以以输入第二行中的顺序驶离车站，输出"Yes"，否则输出"No"。

Sample Input1

4
1 2 3 4

Sample Output1

Yes

Sample Input2

4
4 2 3 1

Sample Output2

No

Zsi-r's solution

#include <iostream>
#include <cstring>
//以1，2，3，4进栈，之后比它大的数要从小到大排
using namespace std;

class seqStack
{
    private:
        int *elem;
        int top_p;
        int maxSize;
        void doubleSpace();
    public:
        seqStack(int initSize = 10);
        ~seqStack();
        bool isEmpty() const;
        void push(int x);
        int pop();
        int top() const;
};

seqStack::seqStack(int initSize)
{
    elem = new int[initSize];
    maxSize = initSize;
    top_p = -1;
}

seqStack::~seqStack()
{
    delete []elem;
}


bool seqStack::isEmpty() const
{
    return top_p==-1;
}


void seqStack::push(int x)
{
    if (top_p==maxSize-1) doubleSpace();
    elem[++top_p] = x;
}


int seqStack::pop()
{
    return elem[top_p--];
}


int seqStack::top() const
{
    return elem[top_p];
}


void seqStack::doubleSpace()
{
    int
 *tmp = elem;

    elem  = new int [2*maxSize];

    for (int i =0;i<maxSize ; i++)
    {
        elem[i]= tmp[i];
    }
    maxSize *=2;
    delete []tmp;
}

int main()
{   
    int Num_of_cars;
    int *cars;
    int count = 1;
    seqStack stage_C;
    cin >> Num_of_cars;

    cars = new int[Num_of_cars];
    for (int i = 0; i < Num_of_cars;++i)
    {
        cin >> cars[i];
    }

    for (int j = 0; j < Num_of_cars;++j)
    {
        while(count != Num_of_cars && (stage_C.isEmpty() || stage_C.top()!=cars[j]))
        {
            stage_C.push(count);
            count++;
        }
        if(stage_C.top()==cars[j])
        {
            stage_C.pop();
            continue;
        }
    }

    if (stage_C.isEmpty())
    {
        cout << "Yes" << endl;
    }
    else
        cout << "No" << endl;

    return 0;
}