华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 1676|回复: 0
打印 上一主题 下一主题

双栈列车调度

[复制链接]

61

主题

147

帖子

563

积分

超级版主

Rank: 8Rank: 8

积分
563
跳转到指定楼层
楼主
发表于 2016-8-11 00:54:10 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
本帖最后由 diggersun 于 2016-8-11 00:56 编辑

2020年,很多工作已经由机器人来担当了,比如X火车站的列车调度员就是一个机器人。X车站很小,其结构如下图所示:
其中,A是车站的入口轨道,D是出口,B和C是两个长度足够的中转轨道(最底端没有出口)。所有的轨道都是单线,即任一时刻,至多只有一辆列车通过,所以,A端列车只能顺次进站,中转轨道B和C中,也只有最顶端的列车(如果有的话)可以移动。
调度员只可以执行下述6种调度操作(当然,他一次只能移动一辆可以移动的列车):
让A端的进站列车进入B,记作A->B;
让A端的进站列车进入C,记作A->C;
让A端的进站列车直接移动到D出站,记作A->D;
让中转轨道B中的顶端列车移动到C的顶端,记作B->C;
让中转轨道B中的顶端列车移动到D出站,记作B->D;
让中转轨道C中的顶端列车移动到D出站,记作C->D。
作为列车调度员,digger的工作是这样的:每天早晨,有N辆列车从A端进站(不妨按进站顺序编号为1..N),然后,他将要按照指令,通过调度操作,使列车按照某个给定的顺序出站。
然而,最近digger向HSY提出了申诉,因为他怀疑有些命令是否真的能够实现。所以,HSY委派你编写一个程序,根据给定的出站序列,判断是否存在可行的调度方案,更进一步的,如果这样的调度方案存在,请找出其中操作步数最少的一种(如有多种这样的方案,只需找到其中的一种即可)。

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持:DZ动力|华师一附中OI组  

GMT+8, 2024-12-26 01:41 , Processed in 0.116764 second(s), 25 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表