出操队形(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)。
具体代码:
 #include <stdio.h>

 int n; //输入的学生个数
int data[];
int longest_x[], r_longest_x[];
int temp_longest[];
int ans; int search_b(int count, int x)
{
int left = , right = count - , mid; while (left <= right)
{
mid = (left + right) / ;
if (temp_longest[mid] == x)
return mid;
else if (temp_longest[mid] < x)
left = mid + ;
else
right = mid - ;
}
return left;
}
void longest_x_f()
{
int i, count = , index; temp_longest[count ++] = data[];
longest_x[] = count;
for (i = ; i < n; i ++)
{
index = search_b(count, data[i]);
if (index == count)
temp_longest[count ++] = data[i];
else
temp_longest[index] = data[i];
longest_x[i] = count;
}
}
void r_longest_x_f()
{
int i, j, count = , index; temp_longest[count ++] = data[n - ];
r_longest_x[n - ] = count;
for (i = n - ; i >= ; i --)
{
index = search_b(count, data[i]);
if (index == count)
temp_longest[count ++] = data[i];
else
temp_longest[index] = data[i];
r_longest_x[i] = count;
}
} int main(void)
{
int i, temp = ; while (scanf("%d", &n) != EOF)
{
for (i = ; i < n; i ++)
scanf("%d", &data[i]);
longest_x_f();
r_longest_x_f();
ans = ;
for (i = ; i <= n - ; i ++)
if (n - (longest_x[i] + r_longest_x[i]) < ans)
ans = n - (longest_x[i] + r_longest_x[i]);
printf("%d\n", ans + );
}
return ;
}

 
上一篇:Java 字符串拆分(拆分字符串)


下一篇:NBUT 1120 Reimu's Teleport (线段树)