Jobdu1500-出操队形[微策略面试题] | Acm之家

微策略2013年校园招聘面试一面试题
九度1500-出操队形[微策略面试题] | Acm之家

在读高中的时候，每天早上学校都要组织全校的师生进行跑步来锻炼身体，每当出操令吹响时，大家就开始往楼下跑了，然后身高矮的排在队伍的前面，身高较高的就要排在队尾。突然，有一天出操负责人想了一个主意，想要变换一下队形，就是当大家都从楼上跑下来后，所有的学生都随机地占在一排，然后出操负责人从队伍中抽取出一部分学生，使得队伍中剩余的学生的身高从前往后看，是一个先升高后下降的"山峰"形状。据说这样的形状能够给大家带来好运，祝愿大家在学习的道路上勇攀高峰。(注，山峰只有一边也符合条件，如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（最长上升子序列长度）的变体。有动态规划解法动态规划(3)-最长递增子序列  和 O(nlogn)算法 的解法。

14	//在arr中找到的大于等于key的第一个数。没有的话，返回n

15	//此处也可以直接调用STL里面的lower_bound函数

16	int lower_bound(int arr[],int n ,int key){

17	if(n == 0) return 0;

18	int low = 0;

19	int high = n-1;

20	while(low <= high){

21	int mid = (low+high)/2;

22	if( arr[mid] < key)

23	low = mid+1;

24

else

25	high = mid-1;

26

}

27	return low;

28

}

29

30	//结果存放在res中，res[i]表示 arr[0...i]的最大上升序列的长度。

31	int lis(int arr[], int n, int res[]){

32	res[0] = 1;

33	int lisSize = 1;

34

int low;

35	for(int i=1; i<n; i++){

36	//或调用系统 的lower_bound

37	/*int * p = lower_bound(arr, arr+lisSize, arr[i]);

38	low = p - arr;*/

39	low = lower_bound(arr, lisSize, arr[i]);

40	//如果超出，更新最大长度

41	if(low >= lisSize) lisSize = low+1;

42	//用arr[i]更新较大的那个值

43	arr[low] = arr[i];

44	res[i] = lisSize;

45

}

46	return lisSize;

47

}

48

49	int main() {

50	//freopen("in.txt", "r", stdin);

51

int n;

52	int * arr, *reverseArr, *res, *reverRes;

53	while(scanf("%d",&n) != EOF){

54	arr = new int[n+1];

55	reverseArr = new int[n+1];

56	res = new int[n+1];

57	for(int i=0; i<n; i++) scanf("%d", &arr[i]);

58	//反向的再计算一次

59	for(int i=0; i<n; i++) reverseArr[i] = arr[n-i-1];

60	lis(arr, n, res);

61	free(arr);

62	reverRes = new int[n+1];

63	lis(reverseArr, n, reverRes);

64	free(reverseArr);

65	int ans = 0;

66	for (int i = 0; i < n; i++) {

67	if (ans < res[i] + reverRes[n - i - 1] - 1)

68	ans = res[i] + reverRes[n - i - 1] - 1;

69

}

70	printf("%d\n", n-ans);

71

}

72

return 0;

73

}

X.  http://blog.csdn.net/JDPlus/article/details/20531307
http://www.xuebuyuan.com/738145.html

1. int BSearch(int dp[], int start, int end, int key){//搜索大于等于key的第一个元素的位置  
2.     int middle;  
3.     while (start <= end){  
4.         middle = ((end - start) >> 1) + start;  
5.         if (dp[middle] < key)  
6.             start = middle + 1;  
7.         else if (dp[middle] > key)  
8.             end = middle - 1;  
9.         else  
10.             return middle;  
11.     }  
12.     return start;  
13. }  
14.   
15. int Insert(int data, int *nMax){//找到以data为结尾的上升子序列的长度，并返回  
16.     int j = BSearch(dp, 0, *nMax, data);  
17.     if (j > *nMax){  
18.         *nMax = j;  
19.         dp[j] = data;  
20.     }  
21.     else if (dp[j-1] < data && data < dp[j]){  
22.         dp[j] = data;  
23.     }  
24.     return j;  
25. }  
26.   
27. void LIS(int n){//求以student[i]为结尾的上升子序列的长度  
28.     int i;  
29.     int nMaxLIS = 1;  
30.     dp[0] = -1;  
31.     dp[1] = student[1];  
32.     cnt[1] = 1;  
33.     for (i = 2; i <= n; ++i){  
34.         cnt[i] = Insert(student[i], &nMaxLIS);  
35.     }  
36. }  
37.   
38. void LDS(int n){//求以student[i]为开头的下降子序列的长度  
39.     int i;  
40.     int nMaxLDS = 1;  
41.     dp[0] = -1;  
42.     dp[1] = student[n];  
43.     for (i = n - 1; i >= 1; --i){  
44.         cnt[i] += Insert(student[i], &nMaxLDS) - 1;  
45.     }  
46. } 
47. int main(void){  
48.     int n, i;  
49.     int max;  
50.     while (scanf("%d", &n) != EOF){  
51.         for (i = 1; i <= n; ++i)  
52.             scanf("%d", &student[i]);  
53.         LIS(n);  
54.         LDS(n);  
55.         max = -1;  
56.         for (i = 1; i <= n; ++i)  
57.             if (max < cnt[i])  
58.                 max = cnt[i];  
59.         printf("%d\n", n - max);  
60.     }  
61.     return 0;  
62. }  

Read full article from 九度1500-出操队形[微策略面试题] | Acm之家