1、题目链接：[NOIP1999 提高组] 导弹拦截 - 洛谷

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N],x,n;
int b[N],len;int main(){while(cin>>x)a[++n]=x;//求最长不上升子序列 b[0]=2e9;//初始化为无穷大for(int i=1;i<=n;i++){if(a[i]<=b[len])b[++len]=a[i];//小则添加 else{int l=1,r=len;while(l<r){int mid=l+r>>1;if(a[i]>b[mid])r=mid;else l=mid+1;}b[l]=a[i]; }}cout<<len<<endl;len=0;//求最长上升子序列b[0]=-2e9;for(int i=1;i<=n;i++){if(a[i]>b[len])b[++len]=a[i];else{int l=1,r=len;while(l<r){int mid=l+r>>1;if(b[mid]>=a[i])r=mid;else l=mid+1;}b[l]=a[i];} } cout<<len<<endl;return 0;
}