题目地址：
- 题目描述：
-
在读高中的时候，每天早上学校都要组织全校的师生进行跑步来锻炼身体，每当出操令吹响时，大家就开始往楼下跑了，然后身高矮的排在队伍的前面，身高较高的就要排在队尾。突然，有一天出操负责人想了一个主意，想要变换一下队形，就是当大家都从楼上跑下来后，所有的学生都随机地占在一排，然后出操负责人从队伍中抽取出一部分学生，使得队伍中剩余的学生的身高从前往后看，是一个先升高后下降的“山峰”形状。据说这样的形状能够给大家带来好运，祝愿大家在学习的道路上勇攀高峰。(注，山峰只有一边也符合条件，如1,1、2,2、1均符合条件)
- 输入：
-
输入可能包含多个测试样例。
对于每个测试案例，输入的第一行是一个整数n(1<=n<=1000000)：代表将要输入的学生个数。 输入的第二行包括n个整数：代表学生的身高（cm）(身高为不高于200的正整数)。
- 输出：
-
对应每个测试案例，输出需要抽出的最少学生人数。
- 样例输入：
-
6100 154 167 159 132 1055152 152 152 152 152
- 样例输出：
-
04
- 来源：
#include#define MAX 1000001int 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) start = middle + 1; else 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]为结尾的上升子序列的长度 int i; int nMaxLIS = 1; dp[0] = -1; dp[1] = student[1]; cnt[1] = 1; for (i = 2; i <= n; ++i){ cnt[i] = Insert(student[i], &nMaxLIS); }}void LDS(int n){//求以student[i]为开头的下降子序列的长度 int i; int nMaxLDS = 1; dp[0] = -1; dp[1] = student[n]; for (i = n - 1; 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上相似的题目：