学步园

初做此题时，的确注意到了数据范围，如果用动态规划做的话，两层搜索，时间复杂度为o(n^2)，n达50000，铁定超时。但是我还是用dp交了一次，果然tle了。想在10001的基础上优化一下，但是苦于没想法。

龙酱后来跟我提了一下 优先队列 这种数据结构。什么是优先队列？

优先队列(priority queue)

普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高进先出（largest-in，first-out）的行为特征。

在优先队列中插入数值和删除数值两种操作的时间复杂度是o(logn)，可以大大提高程序效率。具体的在《挑战程序设计竞赛》这本书里面讲的很清楚，我就是看的这本书理解的。

我做这个题时，参考了这篇文章
最长不下降子序列的O(n^2)算法和O(nlogn)算法 - General的日志 - 网易博客（但是此题是求最长单增子序列）。

做法是用了一个数组来存储子序列信息，但是我不清楚那个数组是不是优先队列，还请各位指教！

具体实现是这样的：

len[i]的下标代表在子序列的长度i，len[i]内储存的值是所有长度为i的单增子序列中结尾元素里值最小的那个。lenth记录len[]的当前长度。则序列读完后，len数组的下标最大值，即为最长单增子序列的长度。

读入序列的第一个元素a1首先放入len[1]，lenth=1，然后读入第二个元素a2。如果a2>=a1，则lenth++，len[lenth]=a2；不然，len[lenth]=a2。同理于a3，a4，……，an，最后得到的lenth就是答案。

做这个题时还使用了一个技巧，就是一种高效的查找元素的方法，二分查找。

二分查找的先决条件是，作为搜索范围的序列首先应该是有序的。

AC代码：

#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
int len[50001] = {0}; //len[i]表示长度为i的子序列中最小的结尾数

int b_search(int x, int l, int r)
{
        while (l <= r)
        {
                int mid = (l + r) >> 1;
                if (len[mid] <= x && len[mid+1] >= x)
                        return mid + 1;
                else if (len[mid] > x)
                        r = mid - 1;
                else
                        l = mid + 1;
        }
        return 1;
}

int main()
{
        int n;

        while (~scanf("%d", &n))
        {
                int i = 1;
                int lenth = 1;

                while (i <= n)
                {
                        int a;
                        scanf("%d", &a);

                        if (i == 1)
                        {
                                len[1] = a;
                        }
                        else
                        {
                                if (a >= len[lenth])
                                {
                                        lenth++;
                                        len[lenth] = a;
                                }
                                else if (a < len[1])
                                {
                                        len[1] = a;
                                }
                                else
                                {
                                        int j = b_search(a, 1, lenth);
                                        len[j] = a;
                                }
                        }
                        i++;
                }
                printf("%d\n", lenth);
        }

        return 0;
}

后来我看了一下龙酱的，竟然可以优化到46毫秒。看了他的源码，原来是没有用scanf读入而是自己写了个读整数函数，果然牛逼。。