拦截导弹
贪心策略如下所示：图一表示具体做法，图二表示证明
上图的证明是指，如果最优解和贪心存在第一个地方不一样，那么因为 \(a\) 是 \(\ge x\) 的最小数，所以 \(b\ge a\)，所以这两段是可以互换的，所以最优解是可以变成贪心的。
性质，\(g\) 数组单调不降，证明如上图。
我们可以惊奇的发现，这个步骤和 896. 最长上升子序列 II 的做法一致，所以就可以用那道题的做法；这道题其实是可以用二分优化的。
#include<bits/stdc++.h>
using namespace std;
int n,x,i,j,d[500001],ans,mid,a[500001],b[500001];
int main(){
while(cin>>a[++n]);
n--;
for(i=n;i>=1;i--)
b[i]=a[n-i+1];
for(i=1;i<=n;i++){
if(b[i]>=d[ans])
d[++ans]=b[i];
else{
mid=upper_bound(d+1,d+1+ans,b[i])-d;
d[mid]=b[i];
}
}
cout<<ans<<endl;
ans=0;
for(i=1;i<=n;i++){
if(a[i]>d[ans])
d[++ans]=a[i];
else{
mid=lower_bound(d+1,d+1+ans,a[i])-d;
d[mid]=a[i];
}
}
cout<<ans;
return 0;
}