首页 > 代码库 > {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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。