https://blog.csdn.net/u014302425/article/details/79981435
/* #include<stdio.h> const int maxn=1e5+5; int main(){ int n; int a[maxn]; scanf("%d",&n); int k, len=0; while(n--){ scanf("%d",&k); if(len==0||k>a[len-1]){ a[len++]=k;//新轨道 } else { int l=0, r=len-1; while(l<r){ int mid=l+(r-l)/2; if(a[mid]>k) r=mid-1; else l=mid+1; } a[l]=k; } } printf("%d",len); return 0; } */ #include<stdio.h> #include<limits.h> #include<string.h> int n; int che[100001]; //che[]用于储存链尾序号 int N; int count =1;//总轨道数 int y; int foun(int n) { //与最后一个相比 if(n>che[count]) return 0; //下面这个感觉没必要 if(n<che[count]&&n>che[count-1]) return count; // for(y=1;y<=count;y++) if(n<che[y]) //检查能否插入 return y; } int main() { scanf("%d",&N); int i,k,a; memset(che,0,sizeof(che)); che[1]=INT_MAX; for(i=1;i<=N;i++) { scanf("%d",&n); if(a=foun(n)) che[a]=n; //更新链尾序号 else //不可插入链尾，则创建新轨道 { count++; che[count]=n; } } printf("%d",count); }
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#include<stdio.h> #include<set> using namespace std; int main() {int n,num;scanf("%d %d",&n,&num);set<int> s;s.insert(num);for(int i=1;i<n;i++){scanf("%d",&num);if(s.lower_bound(num)!=s.end()){s.erase(s.lower_bound(num));}s.insert(num);}printf("%d",s.size());return 0; }
1234567891011121314151617181920理论上来说，用vector后upper_bound更快一些
g++ -DONLINE_JUDGE -fno-tree-ch -O2 -Wall -std=c++14 -pipe $src -lm -o $exe
开O2优化，PTA
