传统题 1000ms 256MiB

列车调度

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

火车站的列车调度铁轨的结构如下图所示。 image

两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入,最后从出口离开。在图中有9趟列车,在入口处按照{8,4,2,5,3,9,1,6,7}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开,则至少需要多少条平行铁轨用于调度?

输入格式:

输入第一行给出一个整数N (2 ≤ N ≤10^5 ),下一行给出从1到N的整数序号的一个重排列。数字间以空格分隔。

输出格式:

在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。

9
8 4 2 5 3 9 1 6 7
4

样列解释:

第1条铁轨:8进入、4进入排在8后面等待、2排在4后面; 第2条铁轨:5进入、3进入排在5后面; 9从第3条进入出去,8从第1条铁轨出; 1可以排在第1条或第2条的后面等待 第3条铁轨:6进入 7从第4条铁轨出。 然后依次出:6、5、4、3、2、1。 所以最少需要4条平行铁轨。

12.08晚6点半练习及作业

未认领
状态
已结束
题目
8
开始时间
2023-12-8 18:15
截止时间
2023-12-14 23:59
可延期
24 小时