{POJ}{3903}{Stock Exchange}{nlogn 最长上升子序列}

Matthewl

　　题意：求最长上升子序列，n=100000
　　思路：O(N^2)铁定超时啊。。。。利用贪心的思想去找答案。利用栈，每次输入数据检查栈，二分查找替换掉最小比他大的数据，这样得到的栈就是更优的。这个题目确实不错，思路很好



#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <memory>
#include <cmath>
#include <bitset>
#include <queue>
#include <vector>
#include <stack>
using namespace std;

#define CLR(x,y) memset(x,y,sizeof(x))
#define MIN(m,v) (m)<(v)?(m):(v)
#define MAX(m,v) (m)>(v)?(m):(v)
#define ABS(x) ((x)>0?(x):-(x))
#define rep(i,x,y) for(i=x;i<y;++i)

const int MAXN = 110000;
int n,m;
int len;
int val;
int s[MAXN];
int BF(int cur)
{
int low,high,mid;
int pre;
low = 0;
high = len-1;
while(low <= high)
{
mid = (low+high)>>1;
if(s[mid]<cur){
low = mid+1;
}
else if(s[mid]>cur){
high = mid-1;
}
else
return mid;
}
return low;
}
void Solve()
{
while(scanf("%d",&n)!=EOF)
{
len = 0;
for(int i = 0 ; i < n; ++i)
{
scanf("%d",&val);
if(len == 0 || s[len-1] < val){
s[len] = val;
++len;
}
else
{
int f = BF(val);
s[f] = val;
}
}
printf("%d\n",len);
}
}
int main()
{
Solve();
return 0;
}