"
题目地址：
题目描述：
在读高中的时候，每天早上学校都要组织全校的师生进行跑步来锻炼身体，每当出操令吹响时，大家就开始往楼下跑了，然后身高矮的排在队伍的前面，身高较高的就要排在队尾。突然，有一天出操负责人想了一个主意，想要变换一下队形，就是当大家都从楼上跑下来后，所有的学生都随机地占在一排，然后出操负责人从队伍中抽取出一部分学生，使得队伍中剩余的学生的身高从前往后看，是一个先升高后下降的“山峰”形状。据说这样的形状能够给大家带来好运，祝愿大家在学习的道路上勇攀高峰。(注，山峰只有一边也符合条件，如1,1、2,2、1均符合条件)
输入： //代码效果参考：https://v.youku.com/v_show/id_XNjQwMDQxMTQ2MA==.html
输入可能包含多个测试样例。
对于每个测试案例，输入的第一行是一个整数n(1<=n<=1000000)：代表将要输入的学生个数。
输入的第二行包括n个整数：代表学生的身高（cm）(身高为不高于200的正整数)。
输出：
对应每个测试案例，输出需要抽出的最少学生人数。
样例输入：
6
100 154 167 159 132 105
5
152 152 152 152 152
样例输出：
0
4
来源： 微策略2013年校园招聘面试一面试题
#include
#define MAX 1000001
int student【MAX】;
int cnt【MAX】;//cnt【i】表示以i为“峰顶”的最长子序列
int dp【MAX】;
int BSearch(int dp【】, int start, int end, int key){//搜索大于等于key的第一个元素的位置
int middle;
while (start <= end){
middle = ((end - start) ] 1) + start;
if (dp【middle】 key)
end = middle - 1;
else
return middle;
}
return start;
}
int Insert(int data, int *nMax){//找到以data为结尾的上升子序列的长度，并返回
int j = BSearch(dp, 0, *nMax, data);
if (j > *nMax){
*nMax = j;
dp【j】 = data;
}
else if (dp【j-1】 < data && data < dp【j】){
dp【j】 = data;
}
return j;
}
void LIS(int n){//求以student【i】//代码效果参考：https://v.youku.com/v_show/id_XNjQwMDQwMzk2OA==.html
为结尾的上升子序列的长度int i;
int nMaxLIS = 1;
dp【0】 = -1;
dp【1】 = student【1】;
cnt【1】 = 1;
for (i = 2; i = 1; --i){
cnt【i】 += Insert(student【i】, &nMaxLDS) - 1;
}
}
int main(void){
int n, i;
int max;
while (scanf(""%d"", &n) != EOF){
for (i = 1; i <= n; ++i)
scanf(""%d"", &student【i】);
LIS(n);
LDS(n);
max = -1;
for (i = 1; i <= n; ++i)
if (max < cnt【i】)
max = cnt【i】;
printf(""%d\n"", n - max);
}
return 0;
}
九度OJ上相似的题目：
"
