A25071. 列车调度
填空题
困难
知识点
题目描述
列车调度
题目描述
火车站的列车调度铁轨的结构如下图所示。
两端分别是一条入口（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参考答案
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
int a[n] = {0};
int x;//每次输入的列车序号
int t = 0;
for (int i = 0; i < n; i++)
{
cin >> x;
if (t == 0 || a[t - 1] < x) //t-1是因为a[t]是0，a[t-1]才是真正的序号
//如果最后一个道路的最后一个元素都比x小，
//说明前几条道路也没有能容下x的了
{
a[t] = x; //第一个进去的，一定是这一列最大的
// printf("t=%d a[%d]=%d x=%d\n",t,i,a[i],x);
t++;
}
int l = 0, r = t, mid; //t代表了当前开辟的道路的数量
while (l < r)
{
mid = (r - l) / 2 + l;
if (x <= a[mid])
{
r = mid;
}
else
l = mid+1 ;
}
a[l] = x;
//测试用：
// for (int j = 0; j < t; j++)
// {
// cout << a[j] << ' ';
// }
// cout << endl;
}
cout << t;
return 0;
}
上一题
下一题