1357:车厢调度(train) ybt

1357:车厢调度(train)

【题目描述】

有一个火车站,铁路如图所示,每辆火车从A驶入,再从B方向驶出,同时它的车厢可以重新组合。假设从A方向驶来的火车有nn节(n≤1000n≤1000),分别按照顺序编号为11,22,33,…,nn。假定在进入车站前,每节车厢之间都不是连着的,并且它们可以自行移动到B处的铁轨上。另外假定车站C可以停放任意多节车厢。但是一旦进入车站C,它就不能再回到A方向的铁轨上了,并且一旦当它进入B方向的铁轨,它就不能再回到车站C。1357:车厢调度(train) ybt

负责车厢调度的工作人员需要知道能否使它以a1a1,a2a2,…,anan的顺序从B方向驶出,请来判断能否得到指定的车厢顺序。

【输入】

第一行为一个整数nn,其中n≤1000n≤1000,表示有nn节车厢,第二行为nn个数字,表示指定的车厢顺序。

【输出】

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

  代码如下:
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1001;
int stack[N],a[N];
int top,n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    top=0;
    for(int i=1,cur=1;i<=n;++i)//cur是当前要从A方向驶入的车厢号
    {
        while(cur<=a[i])
            stack[++top]=cur++;
        if(stack[top]==a[i])
            --top;
        else
        {
            cout<<"NO"<<endl;
            return 0;
        }
    }
    cout<<"YES"<<endl;
    return 0;
}

我所理解的是这样的吗:

原先我有n个元素,是从小到大排列的,我把他们记作cur++,也就是说进栈车厢编号一开始为1;下一个就是cur++也就是2,以此类推,从而满足从小到大依次排列;

现在我让入栈,也就是stack[++top]=cur++;如果栈顶元素==a【i】(也就是你所输入的出栈顺序),我就让stack离开,也就是if(stack[top]==a[i])  --top;一旦我所输入的出栈元素无法与栈顶元素相等,就是无法满足条件,cout<<"NO",否则就是“YES”。

2022/2/20

上一篇:动手学深度学习 | 长短期记忆网络(LSTM)| 57


下一篇:Excel表格中如何隐藏手机号码中间几位