列车调度（25 分）

妖狐艹你老母 2022-05-08 12:42 249阅读 0赞

火车站的列车调度铁轨的结构如下图所示。  
![在这里插入图片描述][20181011210511452]  
两端分别是一条入口（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

## 输出样例： ##

这个题直接用set做还是挺简单的，就是一辆辆列车模拟一下，跟在比自己序号大的列车后面，如果进入车道就更新一下此车道的最小序号。如果当前不存在这种情况就进入一条新的车道。要注意的是单纯的用set会超时，我们可以用一下set中的一个函数：upper\_bound()函数，会直接查找与传入的值最接近的且比其大的数，这样就可以省去内层循环，节省大量时间。  
再就是用二分查找。  
下附一开始的超时代码和AC代码。

下面是超时代码：

#include<bits/stdc++.h>
    using namespace std;
    int a[100001]={
        0};
    set<int>s[100001];
    int main()
    {
        
        int n;
        cin>>n;
        int cnt=0,t=1;
        for(int i=0;i<n;i++){
        
            cin>>a[i];
        }
        s[1].insert(a[0]);
        for(int i=1;i<n;i++)
        {
        
            int f=0;
            for(int j=1;j<=t;j++)
            {
        
                set<int>::iterator it=s[j].begin();
                if(a[i]<*it)
                {
        
                    s[j].insert(a[i]);
                    f=1;
                    break;
                }
            }
            if(f==0)
            {
        
                t++;
                s[t].insert(a[i]);
            }
        }
        cout<<t;
    }

AC代码（1）：

#include<bits/stdc++.h>
    using namespace std;
    int a[100001]={
        0};
    set<int>s;
    int main()
    {
        
        int n;
        cin>>n;
        for(int i=1;i<=n;i++){
        
            cin>>a[i];
        }
        for(int i=1;i<=n;i++){
        
            if(s.upper_bound(a[i])!=s.end()){
        
                s.erase(s.upper_bound(a[i]));
                s.insert(a[i]);
            }
            else s.insert(a[i]);
        }
        cout<<s.size();
    }

AC代码（2）：

#include <bits/stdc++.h>
    using namespace std;
    
    int main()
    {
        
        int n,m;
        cin>>n;
        int a[100001]={
        0};
        int len=0;
        while(n--){
        
            scanf("%d",&m);
            if(len==0||a[len-1]<m){
        
                a[len++]=m;
            }
            else {
        
                int l=0,r=len-1;
                while(l<r){
        
                    int mid=(l+r)/2;
                    if(a[mid]==m)break;
                    if(a[mid]>m)r=mid-1;
                    else l=mid+1;
                }
                a[l]=m;
            }
        }
        cout<<len<<endl;
    }

[20181011210511452]: /images/20220508/679b02e1ef1c4d24b2cc1062e8c7faf2.png