题解：AcWing 6032 车厢调度

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

AcWing：6032. 车厢调度 - AcWing题库

【题目描述】

有一个火车站，铁路如图所示，每辆火车从A AA驶入，再从B BB方向驶出，同时它的车厢可以重新组合。

假设从A AA方向驶来的火车有n nn节，分别按照顺序编号为1 , 2 , 3 , … , n 1,2,3,\dots,n1,2,3,…,n。

假定在进入车站前，每节车厢之间都不是连着的，并且它们可以自行移动到B BB处的铁轨上。

另外假定车站C CC可以停放任意多节车厢。

但是一旦进入车站C CC，它就不能再回到A AA方向的铁轨上了，并且一旦当它进入B BB方向的铁轨，它就不能再回到车站C CC。

负责车厢调度的工作人员需要知道能否使它以a 1 , a 2 , … , a n a_1,a_2,\dots,a_na1​,a2​,…,an​的顺序从B BB方向驶出，请来判断能否得到指定的车厢顺序。

【输入】

第一行为一个整数n nn，表示有n nn节车厢。

第二行为n nn个数字，表示指定的车厢顺序。

【输出】

如果可以得到指定的车厢顺序，则输出一个字符串YES，否则输出NO。

【输入样例】

5 5 4 3 2 1

【输出样例】

YES

【算法标签】

#栈#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineN1005intmain(){intn,a[N],num=0;stack<int>stk;cin>>n;for(inti=1;i<=n;++i)cin>>a[i];for(inti=1;i<=n;++i){//i为出栈序列下标，等待数字a[i]出栈while(stk.empty()||a[i]!=stk.top()){if(++num>n)//如果待入栈数字大于n，则结束{cout<<"NO";return0;}stk.push(num);}stk.pop();}cout<<"YES";return0;}

【运行结果】

5 5 4 3 2 1 YES