天梯题集——列车调度（模拟、二分）-蒲公英云

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

r囧r小猫 2022-12-24 00:50 262阅读 0赞

列车调度

题意

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

关键点：

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

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

解题思路

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

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

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

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

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

#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;
            else
                l = mid+1;
        }
        if(gd[l]<arr[i])
            gd[cnt++] = arr[i];
        else
            gd[l] = arr[i];
    }
    cout<<cnt<<endl;
    return 0;
}