L2-014 列车调度 (25 分)详解

大家好，又见面了，我是你们的朋友全栈君。

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

两端分别是一条入口（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

该题乍看之下不知道是让干什么的，后来我看了别人的博客后才搞懂了这道题的做法。 该题要想让列车按降序输出，那么必须让同一条轨道上的车编号大的先进入，编号小的后进入，而如果一条轨道上编号最小的车的编号如果比要处理的车的编号还要小的话，那么这个该处理的车就必须新开一条轨道去让该车进入，而题目的要求就是要求出需要多少种这样的轨道。从以上分析中，可以得到以下信息：

if(当前编号>所有轨道上的最小编号)
{
	新增轨道并将该编号放入该轨道。
}
else
{
	把该编号放入最接近它的比他稍大一点的轨道中。
	（有同学可能会问为什么要放到最接近他的轨道，这是因为如果有这种情况出现
	{
		输入数据：8 4 2 5 3 9 1 6 
		在编号1进入之前按照伪代码每条轨道是这样过的情况：
		2 4 8
		3 5
		9
		如果将1放到最接近他的第一条轨道中，那么之后的6可以在不增加轨道的情况下放入第三条 
		轨  道，但如果要把1放入第三条轨道，那么就需要再增加一条轨道去放6，显然这样并不是
		最优解。
	}）
}

由于该题只需输出轨道数，所以每个轨道上并不需要记录所有的编号，只需要记录最小的编号即可，所以可以用，通过set进行插入删除等操作，至于如何找寻距离编号最近的轨道，可以直接利用lower_bound()函数，极为方便，而且通过set进行的查找时间复杂度低，不易超时，虽然有同学可能会用数组进行二分查找，但显然不如set方便。 下面给出代码

#include<iostream>
#include<set>
using namespace std;
int main()
{
	int n;
	cin>>n;
	set<int>sc;
	for(int i=0;i<n;i++)
	{
		int k;
		scanf("%d",&k);
		set<int>::iterator it=sc.lower_bound(k);
		if(it!=sc.end())
		{
			sc.erase(it);
			sc.insert(k);
		}
		else
		sc.insert(k);
	}
	cout<<sc.size();
}

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/159399.html原文链接：https://javaforall.cn