题目
【题目描述】
N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，则他们的身高满足T1<...<Ti>Ti+1>…>TK(1<=i<=K)。
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
【输入格式】
输入文件chorus.in的第一行是一个整数N，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti是第i位同学的身高(厘米)。
【输出格式】
输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。
【样例输入】
8
186 186 150 200 160 130 197 220
【样例输出】
4
【数据规模】
对于50%的数据，保证有n<=200；
对于100%的数据，保证有n<=20000，1<=Ti<=1000000。
解析
该题本身平淡无奇，只是一个标准的LIS动态规划。但是！该题扩大了数据范围！
使得本来O（n2）的时间复杂度过不了，于是只有优化（关键是我考试时没怎么注意）。
这里便会有二分查找的优化方法。
思路
枚举中间的人i，以他为终点正向和倒向求两次LIS，用l[i]和r[i]分别表示以i结尾LIS长度。然后ans = n - l[i] + r[i] + 1;
注意到N <= 20000，所以必须使用logN的算法求LIS
使用d[]临时存储LIS，依次将序列中的数a[i]按以下条件加入d[]中：如果a[i] > d[len]（d[len]是d[]中的最后一个数），则d[++len] = a[i]，否则在d[]中找第一个比a[i]**大或等(必须取到=，否则相同的数将不被替换,而是替换成了第一个比它大的数** )的数，将其替换，这样做的目的是使d[]更有可能成为一个更长的序列。我们注意到d[]是一个递增的序列，则在完成查找时可使用二分的方法。
注意在这个过程中存储l[i]和r[i]
代码
#include<iostream>
#include<cstring>
using namespace std; int a[],l[],r[],rem[];
int n; int main()
{
freopen("chorus.in","r",stdin);
freopen("chorus.out","w",stdout); cin>>n;
for(int i=;i<=n;i++) cin>>a[i]; int len=;
for(int i=;i<=n;i++)
{
if(a[i]>rem[len])
{
rem[++len]=a[i];
l[i]=len;
}
else
{
int left=,right=len;
while(left<right)
{
int mid=(left+right)/;
if(rem[mid]>=a[i])right=mid;
//此处必须取到=，否则相同的数将不被替换,而是替换成了第一个比它大的数
else left=mid+;
}
rem[left]=a[i];
l[i]=left;
}
} memset(rem,,sizeof(rem)); len=;
for(int i=n;i>=;i--)
{ if(a[i]>rem[len])
{
rem[++len]=a[i];
r[i]=len;
}
else
{
int left=,right=len;
while(left<right)
{
int mid=(left+right)/;
if(rem[mid]>=a[i])right=mid;
//此处必须取到=，否则相同的数将不被替换,而是替换成了第一个比它大的数
else left=mid+;
}
rem[left]=a[i];
r[i]=left;
}
} int maxx=;
for(int i=;i<=n;i++)
maxx=max(maxx,l[i]+r[i]-); cout<<n-maxx<<endl;
return ;
}