7-11 列车调度 (25分)

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

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

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

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

input：

9 8 4 2 5 3 9 1 6 7

output：

4

解题思路： 二分法思想的确简单，细节真是魔鬼，卡我喉咙卡的好久。 先讲讲为何只需要4条轨道就能调度，这里用到一个队列的思想，创建如下四条队列：

8 4 2 1 5 3 9 6 7

这样，通过比较队头，以队头大的先出队为规则，则出队序列就可以是9 8 7 6 5 4 3 2 1。 从input中读取数据的时候，倘若比队列中最小的队尾数据小，则添加到该队列的队尾处，否则，创建一个新的队列

但为了节省空间，我们完全不需要真的建几个队列来进行模拟，只需要建立一个一维数组，数组中每一个元素的数值来代表队尾元素的值就行了。 再讲这个题目的重点：二分 基于题目所要求的运行时间苛刻，倘若不使用二分查找提交就直接超时了。 创建一个vector数组track，我们用一组随机的数据1,6,6,7来模拟数组原有的元素，假设我们现在要插入一个新的元素5，则在插入前需要对数组中原有的数据进行二分查找，找到数组中既尽量靠前又比元素5大的数字，将此数字6替换成数字5。倘若找不到比5小的数据，则新建一个队列，元素5入队。 AC代码：

#include<iostream> #include "vector" using namespace std; vector<int>track; void BinarySearch(int a){ int l = 0,r = track.size()-1; while (l<r){ int mid = (l+r)/2; if (a<=track[mid]){ r = mid; } else if (a>=track[mid]){ l = mid+1; } } if (r!=-1 && track[r]>=a){ track[r]=a; }else{ track.push_back(a); } } int main(){ //8 4 2 1 //5 3 //9 6 //7 升序二分 int n,temp; cin>>n; while (n--){ cin>>temp; BinarySearch(temp); } cout<<track.size(); }