火车站的列车调度铁轨的结构如下图所示。
两端分别是一条入口（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
代码长度限制
16 KB
时间限制
300 ms
内存限制
64 MB
例举样例的方法，即可知道此题思路:
对于：进入的先后顺序为8 4 2 5 3 9 1 6 7的序列，出来的序列要为9 8 7 6 5 4 3 2 1的递减数列
方法如下：
8 4 2 1
5 3
9 6
7
由于出来的序列是递减的，故大的优先进入轨道，即：每个轨道一定都是递减序列 。
所以得出一下思路：
①创立数组代表轨道，数组元素为每个轨道最新进入的序号，计数器cnt记录轨道个数。
②由上面的例子可知，在进入序列中如出现比目前所有轨道的最新元素序号都要大的序号，为了保证轨道上的递减性。则需要开创一个新的轨道。
③对于当前进入的轨道的不是②情况的元素，考虑将它放入最靠前的符合要求的轨道（保证轨道数目最优）。这样也保证了每个轨道最新的元素的有序性（递增）。
④由③可知最新元素是递增的，故在进行②的判断是只需判断最新创立的轨道的最新元素。
具体代码如下://不知道为什么部分样例出现了段错误。。。
#include<stdio.h>
int main()
{
int i, j, cnt = 1,n;
int a[10000], b[10000];
scanf("%d", &n);
//进入序列
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
b[0] = a[0];//第一个轨道录入
for (i = 1; i < n; i++)
{
if (a[i]>b[cnt - 1])
{
b[cnt] = a[i];
cnt++;
}
else
{
for (j = 0; j < cnt; j++)
{
if (a[i] < b[j])
{
b[j] = a[i]; break;
}
}
}
}
printf("%d\n", cnt);
return 0;
}这种代码不会出现段错误（然而我的编译器vs2013 .c文件不支持这种写法），但是有一个样例超时：(段错误可能原因：PAT 段错误的原因和解决方法)文章来源：https://www.toymoban.com/news/detail-734270.html
#include<stdio.h>
int main()
{
int i, j, cnt = 1,n;
scanf("%d", &n);
int a[n], b[n];
//进入序列
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
b[0] = a[0];//第一个轨道录入
for (i = 1; i < n; i++)
{
if (a[i]>b[cnt - 1])
{
b[cnt] = a[i];
cnt++;
}
else
{
for (j = 0; j < cnt; j++)
{
if (a[i] < b[j])
{
b[j] = a[i]; break;
}
}
}
}
printf("%d\n", cnt);
return 0;
}另外查找可以优化为二分查找（更快）:文章来源地址https://www.toymoban.com/news/detail-734270.html
#include<stdio.h>
int main()
{
int i, j, cnt = 1,n;
scanf("%d", &n);
int a[n], b[n];
//进入序列
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
b[0] = a[0];//第一个轨道录入
for (i = 1; i < n; i++)
{
if (a[i]>b[cnt - 1])
{
b[cnt] = a[i];
cnt++;
}
else
{
int l = 0, r = cnt - 1;
while (l < r)
{
int mid = l + (r - l) / 2;
if (a[i] < b[mid])
r = mid - 1;
else if (a[i]>b[mid])
l = mid + 1;
}
b[r] = a[i];
}
}
printf("%d\n", cnt);
return 0;
}到了这里，关于列车调度（数据结构）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
