火车排序(栈的基础运用）

84 阅读 0 评论 56 点赞

我是靠谱客的博主务实路人，最近开发中收集的这篇文章主要介绍火车排序(栈的基础运用），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述

某城市有一个火车站，铁轨铺设如图所示

A线出来的火车只能驶入C线，C线驶出的火车只能驶入B线。（即：A -> C -> B）

当然，火车也可以在C线停留，我们认为C线的容量是无限大的。

P.S. 对于后进入C线的火车，应该先从C线离开

现在有一些从A线驶入的火车，但它没有按照编号依次升序进入，现在想要借助C线，使得从B线驶出的火车，按照编号升序依次驶出。

你认为火车能通过选择正确的换线方式，使得它有序驶出么？

如果有可能，请输出“YES”，否则输出“NO”

输入格式

输入数据有两行

第一行为一个正整数n，表示火车的数量(n不超过1000)

第二行包括n个正整数，为火车的编号，保证编号在[1,n]内且不重复。

输出格式

“YES” 或 “NO”

不带引号

样例输入

样例1：

3 2 1

样例2：

2 3 1

样例输出

样例1：

YES

样例2：

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector> 
#include <map>
#include <stack>
#include <queue>
using namespace std;
typedef long long ll;
int w[300105];
int b[2102105];
const int maxx = 40010;
int n,m,r,k,t,num,now,p;
const double pi=acos(-1.0); 
stack <int> e;//初始化栈 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;//输入车辆数目 
    int num = 1; 
    while(n --)
    {
        cin >> m;//输入 车辆编号 
        e.push(m);//推入栈中 
        while(e.empty() == 0&&e.top() == num)//如果栈非空并且栈顶等于1//因为题目的要求是按次序走出 
        {
            e.pop();//删去栈顶 
            num ++;//num++进行下一次判断 
        }
    }
    if(e.empty() == 1)//如果已经是空的了那么说明符合题目要求，所有火车均走出 
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }
    return 0;
}