天梯题集——列车调度（模拟、二分）

天梯题集——列车调度（模拟、二分）"/>

天梯题集——列车调度（模拟、二分）

列车调度

题意

这道题题意容易混淆，认为一条轨道只能停留一辆火车，其实不然，题目中每条轨道都可排列无数辆递减的火车。

关键点：

①、按入口顺序排列火车
②、排列的每条轨道火车序号必须单调递减，否则增加新轨道
按样例来说（圆形编号为轨道编号，数字编号为火车编号）

有了以上的认识，问题就简单了。

解题思路

①、维护轨道数组
维护一个轨道数组，代表每条轨道的末端火车序号。

②、维护规则
若当前要添加的火车序号大于每条轨道的末端火车编号，那么就开辟一条新的轨道放置当前要添加的火车。

题目要求是最少条轨道数，我们必须从第一条轨道遍历到最后一条轨道，若存在则直接将当前轨道的最小编号替换为当前要添加的火车编号，完成添加，否则开辟新的轨道。

③、二分优化
按照维护规则的逻辑，我们能够发现轨道与轨道之间的末端火车编号其实是单调递增的。为了提高效率，我们可以通过 二分法 来寻找大于当前要添加的火车编号的最小轨道编号。

④、输出最终得到的最小轨道数

#include<bits/stdc++.h>
using namespace std;
int gd[100010], arr[100010];
int main(){int n;cin>>n;for(int i=0; i<n; i++)cin>>arr[i];int cnt=0;gd[cnt++]=arr[0];for(int i=1; i<n; i++){int flag=0;int l=0, r=cnt-1;while(l<r){int mid = (l+r)/2;if(gd[mid]>arr[i])r = mid;elsel = mid+1;}if(gd[l]<arr[i])gd[cnt++] = arr[i];elsegd[l] = arr[i];}cout<<cnt<<endl;return 0;
}