题目地址：HDU 1950
这题是求最长上升序列，但是普通的最长上升序列求法时间复杂度是O(n*n)，显然会超时。于是便学了一种O(n*logn)的方法。也很好理解。感觉还用到了一点贪心的思想。
具体的见这篇博客吧，写的很通俗易懂。传送门
代码如下：
#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define LL long long int a[50000], b[50000], len; int bin_seach(int x) { int low=1, high=len, mid, ans; while(low<=high) { mid=low+high>>1; if(b[mid]>=x) {high=mid-1;ans=mid;} else low=mid+1; } return ans; } int main() { int t, n, i, pos; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=0;i b[len]) { b[++len]=a[i]; } else { pos=bin_seach(a[i]); b[pos]=a[i]; } } printf("%d\n",len); } return 0; }