例可能1号火车驶入了火车站中的休息区s,在驶出之前2号火车驶入了。那么在这种情况下,1号火车需要等待2号火车倒车出去后才能出去(显然被后面驶入的2号火车挡住了,这个休息区s只有一个出入口)。 出于好奇,小美统计了近些天的火车驶入驶出情况,开始统计和结束统计时休息区s中均是空的。由于中途疏忽,小美觉得自己好像弄错了几个驶入驶出顺序,想请你帮她验证一下.值得注意的是,小美虽然可能弄错了顺序,但对火车的记录是不重不漏的。 形式化地来形容休息区s,我们视其为一个容量无限大的空间,假设两列火车i和j同时处于休息区s中,驶入时刻T;n满足T;n(i)<Tin0j),则驶出时间Tout必定满足Toutl1)>Tout):即,先进后出。
时间: 2023-05-26 22:06:59 浏览: 90
思路:模拟栈操作,使用一个栈来表示休息区中的火车,每次有新的火车到达,如果栈顶的火车比它先进入,则可以直接入栈,否则需要等到栈顶火车出栈后才能进入;每次火车驶离时,只有栈顶火车是当前要驶离的火车时才可以出栈,否则需要等待栈顶火车驶离后才能出栈。
具体实现:
定义一个栈来表示休息区s中的火车,初始化为空栈。
对于每一组查询,按照驶入时间从小到大排列。
遍历每一组查询,根据驶入时间判断是否需要等待前一组火车驶离之后再进入。
如果需要等待,则将当前火车入栈。
否则,如果栈顶火车的驶离时间比当前火车的驶入时间晚,则需要等待栈顶火车驶离后再进入,将当前火车入栈。
否则,当前火车可以直接进入,不需要等待,将其驶离时间记录下来,并弹出栈顶火车直到栈顶火车的驶离时间晚于当前火车的驶入时间为止。
最后如果栈为空,则表示所有火车都能按照规定驶离,否则,栈中剩余的火车无法按照规定驶离。
实现过程中需要注意边界条件的处理,以及时间的升序排列。
阅读全文