题目：传送门
题目大意：有一些士兵站成一排，一开始他们是按编号站的，但是他们的首领不喜欢这样，于是首领让一些人出列，剩下的人中每个人都可以看向左边或右边的远方（即每个人的身高是队列左端或右端到他的所有士兵里唯一最高的）。输出这些士兵的身高，求最少出列几个人可以满足首领的要求。
分析：解法很明确，分别求得队列从前往后和从后往前的LIS，然后再枚举身高最高分别出现的位置，以求得调整后队列的最大人数_max，则ans=n-_max。首先，求LIS有O(nlogn)的算法，具体参见文章，这个算法实际是保存了各种长度LIS的最末尾元素，以便后续对LIS做出调整，这里可以使用单调栈来维护，用笔写写过程能更好的理解这个算法的思想。还有就是注意二分查找的写法了，细节非常多，关于各种二分的写法，分享一篇文章吧。最后再讲一个细节，那就是位运算<<和>>的运算优先级是比+、-都低的，在使用的时候应该注意。
代码：
#include <iostream> #include <algorithm> #include <cmath> #include <cstring> using namespace std; const int MAXN=1005; double h[MAXN]; int l[MAXN]; int r[MAXN]; double lstk[MAXN]; double rstk[MAXN]; int n; void solve(){ int _max; int ltop=0,rtop=0; lstk[ltop]=rstk[rtop]=0.0; for(int i=0;i<n;++i){ if(h[i]>lstk[ltop]){ lstk[++ltop]=h[i]; } else{ int lb=1,rb=ltop,m; while(lb<rb){ m=lb+(rb-lb)/2; if(lstk[m]<h[i]) lb=m+1; else rb=m; } lstk[rb]=h[i]; } l[i]=ltop; } for(int i=n-1;i>=0;--i){ if(h[i]>rstk[rtop]){ rstk[++rtop]=h[i]; } else{ int lb=1,rb=rtop,m; while(lb<rb){ m=lb+(rb-lb)/2; if(rstk[m]<h[i]) lb=m+1; else rb=m; } rstk[rb]=h[i]; } r[i]=rtop; } _max=max(l[n-1],r[0]); for(int i=0;i<n;++i){ for(int j=i+1;j<n;++j){ _max=max(_max,l[i]+r[j]); } } cout<<n-_max<<endl; } int main(){ ios::sync_with_stdio(false); cin>>n; for(int i=0;i<n;++i){ cin>>h[i]; } solve(); return 0; }