出操队形（LIS）

题目来源：微策略2013年校园招聘面试一面试题
题目描述：: 在读高中的时候，每天早上学校都要组织全校的师生进行跑步来锻炼身体，每当出操令吹响时，大家就开始往楼下跑了，然后身高矮的排在队伍的前面，身高较高的就要排在队尾。突然，有一天出操负责人想了一个主意，想要变换一下队形，就是当大家都从楼上跑下来后，所有的学生都随机地占在一排，然后出操负责人从队伍中抽取出一部分学生，使得队伍中剩余的学生的身高从前往后看，是一个先升高后下降的“山峰”形状。据说这样的形状能够给大家带来好运，祝愿大家在学习的道路上勇攀高峰。(注，山峰只有一边也符合条件，如1,1、2,2、1均符合条件)

输入：: 输入可能包含多个测试样例。
对于每个测试案例，输入的第一行是一个整数n(1<=n<=1000000)：代表将要输入的学生个数。
输入的第二行包括n个整数：代表学生的身高（cm）(身高为不高于200的正整数)。

输出：: 对应每个测试案例，输出需要抽出的最少学生人数。

样例输入：

6
100 154 167 159 132 105
5
152 152 152 152 152

样例输出：

0
4

思路：
这道题目直接使用两次LIS就可以了，一次从前往后，一次从后向前。然后分别假设每个人为最高的人，分别算出他前面和后面需要去掉的人的和，最后在其中找最小的就可以了。为了防止超时，在计算LIS的时候使用二分来查找要插入的位置，算法的复杂度为O(nlgn)。
具体代码：

 1 #include <stdio.h>
 2 
 3 int n; //输入的学生个数
 4 int data[1000005];
 5 int longest_x[1000005], r_longest_x[1000005];
 6 int temp_longest[1000005]; 
 7 int ans;
 8 
 9 int search_b(int count, int x)
10 {
11     int left = 0, right = count - 1, mid;
12 
13     while (left <= right)
14     {
15         mid = (left + right) / 2;
16         if (temp_longest[mid] == x)
17             return mid;
18         else if (temp_longest[mid] < x)
19             left = mid + 1;
20         else
21             right = mid - 1;
22     }
23     return left;
24 }
25 void longest_x_f()
26 {
27     int i, count = 0, index;
28 
29     temp_longest[count ++] = data[0];
30     longest_x[0] = count;
31     for (i = 1; i < n; i ++)
32     {
33         index = search_b(count, data[i]);
34         if (index == count)
35             temp_longest[count ++] = data[i];
36         else
37             temp_longest[index] = data[i];
38         longest_x[i] = count;
39     }
40 }
41 void r_longest_x_f()
42 {
43     int i, j, count = 0, index;
44 
45     temp_longest[count ++] = data[n - 1];
46     r_longest_x[n - 1] = count;
47     for (i = n - 2; i >= 0; i --)
48     {
49         index = search_b(count, data[i]);
50         if (index == count)
51             temp_longest[count ++] = data[i];
52         else
53             temp_longest[index] = data[i];
54         r_longest_x[i] = count;
55     }
56 }
57 
58 int main(void)
59 {
60     int i, temp = 0;
61 
62     while (scanf("%d", &n) != EOF)
63     {
64         for (i = 0; i < n; i ++)
65             scanf("%d", &data[i]);
66         longest_x_f();
67         r_longest_x_f();
68         ans = 200000002;
69         for (i = 0; i <= n - 1; i ++)
70             if (n - (longest_x[i] + r_longest_x[i]) < ans)
71                 ans = n - (longest_x[i] + r_longest_x[i]);
72         printf("%d
", ans + 1);
73     }
74     return 0;
75 }

View Code