首页 > ACM题库 > 九度OJ > 九度1500-出操队形[微策略面试题]
2014
07-10

九度1500-出操队形[微策略面试题]

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

分析:

这个是LIS(最长上升子序列长度)的变体。有动态规划解法动态规划(3)-最长递增子序列  和 O(nlogn)算法 的解法。

这里时间卡的比较紧,应该用O(nlog n)的算法。先总体求递增子序列的长度,再求递减子序列的长度。这里为了复用LIS函数,把原来的数组逆序一下,再次调用LIS,就相当于求递减子序列的长度了。

最后遍历一遍,找出在某一点可以达到的总和的最大长度。

代码如下:

//============================================================================
// Name        : 出操队形.cpp
// Author      : Coder
// Version     :
// Copyright   : www.acmerblog.com
// Description : http://ac.jobdu.com/problem.php?pid=1500
//============================================================================

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

//在arr中找到的大于等于key的第一个数。没有的话,返回n
//此处也可以直接调用STL里面的lower_bound函数
int lower_bound(int arr[],int n ,int key){
	if(n == 0) return 0;
	int low = 0;
	int high = n-1;
	while(low <= high){
		int mid = (low+high)/2;
		if( arr[mid] < key)
			low = mid+1;
		else
			high = mid-1;
	}
	return low;
}

//结果存放在res中,res[i]表示 arr[0...i]的最大上升序列的长度。
int lis(int arr[], int n, int res[]){
	res[0] = 1;
	int lisSize = 1;
	int low;
	for(int i=1; i<n; i++){
		//或调用系统 的lower_bound
		/*int * p = lower_bound(arr, arr+lisSize, arr[i]);
		low = p - arr;*/
		low = lower_bound(arr, lisSize, arr[i]);
		//如果超出,更新最大长度
		if(low >= lisSize) lisSize = low+1;
		//用arr[i]更新较大的那个值
		arr[low] = arr[i];
		res[i] = lisSize;
	}
	return lisSize;
}

int main() {
	//freopen("in.txt", "r", stdin);
	int n;
	int * arr, *reverseArr, *res, *reverRes;
	while(scanf("%d",&n) != EOF){
		arr = new int[n+1];
		reverseArr = new int[n+1];
		res = new int[n+1];
		for(int i=0; i<n; i++) scanf("%d", &arr[i]);
		//反向的再计算一次
		for(int i=0; i<n; i++) reverseArr[i] = arr[n-i-1];
		lis(arr, n, res);
		free(arr);
		reverRes = new int[n+1];
		lis(reverseArr, n, reverRes);
		free(reverseArr);
		int ans = 0;
		for (int i = 0; i < n; i++) {
			if (ans < res[i] + reverRes[n - i - 1] - 1)
				ans = res[i] + reverRes[n - i - 1] - 1;
		}
		printf("%d\n", n-ans);
	}
	return 0;
}

ACM之家原创:http://www.acmerblog.com/jiudu-1500-5945.html