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

输入格式:

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

输出格式:

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

输入样例:

1
2
9
8 4 2 5 3 9 1 6 7

输出样例:

1
4

解题思路

这题就是问：在一个1-N的重排列中最少有几个递增子序列。
将这N个数按照输入的顺序依次处理，队列中某一位置的元素表示该递增子序列中最大的元素，这里用到的是贪心的思想：初始队列为空，把第一个输入数据入队，接下来每一个输入数据判断：若队列中存在一个比他小的元素，更新该元素为新的输入数据；若不存在，则该元素入队。（贪心的证明略）
如果不加优化的话，就是每个数据判断的时候需要遍历一遍当前队列，时间复杂度为O(n2)。n的范围为[2,1e5]，时间限制300ms显然不能暴力，需要对队列进行一些改进。
最简单的方法就是，用一个变量存当前要处理的数据前一个数据是什么，比如题目给出的输入样例8、4、2、5、3、9、1、6、7，处理4的时候前一个数据就是8，在遍历队列前加一个判断，若前一个数据比当前数据小，则当前数据直接更新在前一个数据的位置，否则再遍历队列。

如果精益求精的话，可以再加用一个优先队列，或者直接换一个数据结构来表示这个队列。因为是L2的题，没必要花时间写那么复杂，能过就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N=1e5+10;

int q[N];

int main()
{
    int t;
    cin>>t;
    memset(q,0x3f,sizeof q);
    
    int i=0;
    int a=0,b=0;
    int res=0;
    while(t--)
    {
        cin>>a;
        if(a<b)i=0;
        while(q[i]<a)i++;
        q[i]=a;
        res=max(res,i);
        b=a;
    }
    cout<<res+1<<endl;
    return 0;
}