列车调度

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

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

输入格式：

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

输出格式：

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

先看个错误的例子

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int main()
{
	int a[100000];
	int n,i,j,l=0;
	cin>>n;
	int elem,min,max,sign;
	for(i=1;i<=n;i++)
	{
		cin>>elem;
		if(i==1)
		{
			l++;a[l]=elem;max=elem;continue;
		}
		
		if(elem>max)
		{
			l++;a[l]=elem;max=elem;
		}
		else
		{
			if(l==1)
			{
				a[l]=elem;max=elem;
			}
			sort(a,a+l);
			for(j=1;j<=l;j++)
			{
				if(elem>a[j]&&elem<a[j+1])
				{
					
					if(max==a[j+1])
					{
						max=elem;
					}
					a[j+1]=elem;
				}
			}
		}
	}
	cout<<l;
	return 0;
}

基本思路是用数组存每个轨道的末端值，如果大于最大值就另开，否则就查询最接近输入值的并替换。但是有个点超时了，于是用了set（默认升序）；

#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
int main()
{
	set<int> s;
	int n,i,j;
	cin>>n;
	int elem;
	for(i=1;i<=n;i++)
	{
		cin>>elem;
		if(i==1)
		{
			s.insert(elem);continue;
		}
		
		if(s.lower_bound(elem)!=s.end())
		{
			s.erase(s.lower_bound(elem));
		}
		
		s.insert(elem);
	}
	cout<<s.size();
	return 0;
}

s.lower_bound()返回大于输入值的最小值，也就是最接近的值。如果不是最大值，就删除。如果是最大值或者没有，就新加轨道（s.insert())。

原文：https://javaforall.cn/159406.html