算法思想(贪心+二分) $O(nlogn)$
Q1:求一遍最长下降子序列
Q2:维护一个单调上升序列,序列中的每一个数代表了一个拦截系统的最后一个导弹高度
(每一个拦截系统也是一个下降子序列)
C++ 参考代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],f[N],g[N],n,ans1,ans2;
int main(){
while(cin>>a[n]) n++;
for(int i=n-1;i>=0;i--){
int k=upper_bound(f,f+ans1,a[i])-f;
f[k]=a[i];
if(k==ans1) ans1++;
}
cout<<ans1<<endl;
for(int i=0;i<n;i++){
int k=lower_bound(g,g+ans2,a[i])-g;
g[k]=a[i];
if(k==ans2) ans2++;
}
cout<<ans2;
return 0;
}