某地有一处地铁站,轨道铺设如下图所示。 有n(n<=2000)节车厢从A方向驶入车站,进站顺序编号为1~n。试编程实现:判断能否让车厢按指定顺序进入B方向轨道,并驶出车站。过程中可利用C处铁轨实现中转。要求:每节车厢一旦从A移入C,就不能返回A了;一旦从C移入B,就不能返回C了;即在任意时刻只有两种选择:A到以和C到B。输入:输入包含多组数据,每一组数据,第1行是一个整数n。接下来若干行代表1~n车厢的出栈顺序;最一行只有一个整数0,代表本组数据结束。输出:根据判断结果(即能否按指定顺序延指定方向驶出车站)单行输出“Yes”或“No" 输入样例:51 2 3 4 55 4 1 2 3066 5 4 3 2 10 输出样例:YesNo Yes
时间: 2023-03-02 13:25:20 浏览: 107
某地公交车 报站屏幕显示方案
题目描述:给定一个地铁站,轨道的结构如下图所示。假设有n节车厢按照从A方向进入车站的顺序编号为1~n,现在要判断是否能按照给定的顺序进入B方向轨道并离开车站。在过程中,可以利用C处的轨道进行中转。每节车厢一旦从A移入C,就不能返回A;一旦从C移入B,就不能返回C。因此,在任意时刻,只有两种选择:从A到C和从C到B。
输入:输入包含多组数据,每组数据第一行是一个整数n。接下来若干行代表1~n车厢的出栈顺序;最后一行只有一个整数0,代表本组数据结束。
输出:对于每一组数据,如果能够按照给定的顺序进入B方向轨道并离开车站,输出“Yes”,否则输出“No”。
解题思路:模拟题,可以使用一个栈来模拟整个过程。假设输入的车厢出栈顺序为out_order,从1到n遍历out_order,将当前遍历到的车厢压入栈中,同时检查栈顶元素是否等于当前遍历到的出栈顺序。如果栈顶元素等于当前的出栈顺序,则将栈顶元素弹出,否则继续将车厢压入栈中。在整个过程中,需要判断是否有车厢从C移入B,如果是,就需要检查当前的栈顶元素是否等于B方向轨道上的最后一节车厢。如果不等,则不能满足要求。如果最后栈为空,则说明所有车厢都已经按照指定顺序进入B方向轨道并离开车站。
代码实现如下:
阅读全文