列车调度(贪心)

大家好，又见面了，我是你们的朋友全栈君。

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

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

输入格式：

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

输出格式：

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

输入样例：

98 4 2 5 3 9 1 6 7

输出样例：

4

#最初做的时候认为一条轨道只能停留一辆火车，还以为答案错了—_—

#此题对于使用贪心的理解：

我们需要尽量减少加轨道条数，也就是新的火车最好能到一条路线的末尾排着，而为了之后的顺序输出，一条轨道上后面的车需要比前面的编号小，这就产生了选择问题。选择时可以归结出以下逻辑：

选择时要减少轨道条数，增加轨道条数的条件是需要进入的火车大于所有链尾序号，所以为了减小这个条件的成立可能性，就需要使每条轨道尽量多地容纳。举个例子，比如我们现在有两条轨道，轨道上的链尾为轨道一：5号，轨道二：8号，我们需要插入4号车，如果将4号插入轨道二，轨道二上4到8之间的插入可能性就被夺取了，同等条件下，将4号插入5号，相当于没有夺取其他任何可插入的可能性。而我们的目的就是增大可以不加轨道条数的可能性（等价于增大链尾能插入的可能性，又等价于增大链尾能插入的数量），所以需要做的是将新的元素插入到与这个元素序号差别最小的链尾。

#使用贪心策略将火车排入轨道后一定能顺序排出，故不需要考虑排出。

#处于效率考虑，需进行一些逻辑的处理。比如，整个过程是没有必要遍历的，我们从第一个轨道开始，其实相当于划分了轨道上序号的范围，由于序号没有重复的，第二个轨道的序号永远会比第一个轨道大。运用这个规律，只要判定最后一条轨道的链尾序号与需插入的相比，就可以确定是否需要建立新轨道。如果不需要建立新轨道，插入的轨道就是从第一条开始遇到的第一个可以插入的轨道。

#代码实现1(二分)：

#include<stdio.h>
const int maxn=1e5+5;


int main(){
    int n;
    int a[maxn];
    scanf("%d",&n);
    int k, len=0;
    while(n--){
        scanf("%d",&k);
        if(len==0||a[len-1]<k){
            a[len++]=k;
        }else{
            int l=0, r=len-1;
            while(l<r){
                int mid=l+(r-l)/2;
                if(a[mid]>k)
                    r=mid-1;
                else l=mid+1;
            }
            a[l]=k;
        }
    }
    printf("%d",len);
    return 0;
}

#代码实现2：

#include<stdio.h>
#include<limits.h>
#include<string.h>
int n;
int che[100001];          //che[]用于储存链尾序号
int N;
int count =1;

int foun(int n)
{

    if(n>che[count])
        return 0;
    if(n<che[count]&&n>che[count-1])
        return count;

    for(y=1;y<=count;y++)
       if(n<che[y])    //检查能否插入
             return y;

}
int main()
{
    scanf("%d",&N);
    int i,k,a;
    memset(che,0,sizeof(che));

    che[1]=INT_MAX;
    for(i=1;i<=N;i++)
    {
        scanf("%d",&n);
        if(a=foun(n))
            che[a]=n;   //更新链尾序号
        else                 //不可插入链尾，则创建新轨道
        {
            count++;
            che[count]=n;
        }
    }
     printf("%d",count);

}