首页 > 代码库 > L2-014. 列车调度
L2-014. 列车调度
火车站的列车调度铁轨的结构如下图所示。
Figure
两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入,最后从出口离开。在图中有9趟列车,在入口处按照{8,4,2,5,3,9,1,6,7}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开,则至少需要多少条平行铁轨用于调度?
输入格式:
输入第一行给出一个整数N (2 <= N <= 105),下一行给出从1到N的整数序号的一个重排列。数字间以空格分隔。
输出格式:
在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。
输入样例:
9 8 4 2 5 3 9 1 6 7
输出样例:
4
这题我在网上看了一下题解,讲了Dilworth定理,没看懂啥意思,但是这个程序有点简单,
领悟到了,但说不出来,作为一个打酱油的,还是太菜了。
#include <iostream> using namespace std; int dp[111111]; int main() { int n,x; scanf("%d",&n); int len = 0; while(n--) { scanf("%d",&x); if(len == 0 || dp[len-1] <= x) dp[len++] = x; else { int l = 0,r = len-1; while(l <= r) { int mid = (l+r)/2; if(dp[mid] <= x) l = mid+1; else r = mid-1; } dp[l] =x; } } printf("%d\n",len); return 0; }
。
L2-014. 列车调度
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。