P1162 列车编组问题

本文主要是介绍P1162 列车编组问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、原题呈现

1、题目描述

某火车站铁轨铺设如图，有 n 节车厢自 A 方向进入车站，按进站方向编号为 1 ~ n。现对其进行
编组，编组过程可借助中转站 Station，其中 Station 可停靠任意多车厢，由于 Station 末端封
顶，故驶入 Station 的车辆必须按相反方向驶出。对每个车厢，一旦自 A 进入 Station，就不能
再驶入 A；且一旦自 Station 驶入 B，再不能返回 Station。给定 n 值，请判断某个车厢编组是
否可能。

2、输入描述

有多组输入，每组输入占两行。
第一行是车厢节数 n，第二行是 1, 2, ..., n 的一个排列。

3、输出描述

针对每种出站方案，输出该方案是否可行的判断结果。

4、样例输入

5
1 2 3 4 5
5
5 4 1 2 3
6
6 5 4 3 2 1

5、样例输出

Yes
No
Yes

二、思路分析

1、思想转化

本题其实就是栈的应用，Station就是栈
对于所谓不需要进入Station的，可以理解为进入Station后立刻出去
然后判断给出的出栈结果是否有对应的入栈出栈方案

2、用数组构建栈的思想

// 内容		数组/变量	示例		遍历下标	
// 出站方案 station 		1 2 3 4 5 	i
// 火车 	train		1 2 3 4 5	train 
// 临存 	re						loc
// temp为标记位，是否可以有对应出栈方案
int i, j, re[11000] = {0}, station[11000] = {0}, temp = 1, train = 1, loc = 1;
//输入
for(i = 0; i < n; i++)cin>>station[i];
// 第一辆车默认进站
i = 0, re[1] = 1;

3、分析情况

// 车全部进出结束
while(i <= n) {// 此时栈中的火车编号和需要的列车编号相同if(station[i] == re[loc])// 火车出栈，需求的火车数组下标+1i++, loc--;// 因为进栈编号永远是越来越大，所以当需求的火车编号比栈顶火车编号大的时候，说明需要的火车还在后面，那就将火车继续进栈else if(station[i] > re[loc])re[++loc] = ++train;// 否则此时需要的火车在栈里，但不在栈顶，无法出栈，因此为falseelse {temp = 0;break;}
}

三、整体代码

#include<bits/stdc++.h> using namespace std;int main() {int n;while(cin>>n) {int i, j, re[11000] = {0}, station[11000] = {0}, temp = 1, train = 1, loc = 1;for(i = 0; i < n; i++)cin>>station[i];i = 0, re[1] = 1;// 出站方案 station 1 2 3 4 5 	i// 火车 	train	1 2 3 4 5	train // 临存 	re					locwhile(i <= n) {if(station[i] == re[loc])i++, loc--;else if(station[i] > re[loc])re[++loc] = ++train;else {temp = 0;break;}}if(temp)cout<<"Yes"<<endl;elsecout<<"No"<<endl;}return 0;
}

这篇关于P1162 列车编组问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---