首页 > 代码库 > {POJ}{3903}{Stock Exchange}{nlogn 最长上升子序列}

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

题意:求最长上升子序列,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;}