华为机试HJ24 合唱队
描述
N 位同学站成一排，音乐老师要请最少的同学出列，使得剩下的 K 位同学排成合唱队形。
设K位同学从左到右依次编号为 1，2…，K ，他们的身高分别为T1,T2,…,TK ，若存在i(1≤i≤K) 使得T1<T2<......<Ti−1<Ti 且 Ti>Ti+1>......>TK，则称这K名同学排成了合唱队形。
通俗来说，能找到一个同学，他的两边的同学身高都依次严格降低的队形就是合唱队形。
例子：
123 124 125 123 121 是一个合唱队形
123 123 124 122不是合唱队形，因为前两名同学身高相等，不符合要求
123 122 121 122不是合唱队形，因为找不到一个同学，他的两侧同学身高递减。
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
注意：不允许改变队列元素的先后顺序 且 不要求最高同学左右人数必须相等
数据范围： 1≤n≤3000
输入描述：
用例两行数据，第一行是同学的总数 N ，第二行是 N 位同学的身高，以空格隔开
输出描述：
最少需要几位同学出列
示例1
输入：
8 186 186 150 200 160 130 197 200输出：
4说明：
由于不允许改变队列元素的先后顺序，所以最终剩下的队列应该为186 200 160 130或150 200 160 130
一、问题分析
首先读题，仔细看描述中的内容，发现需求是
1.N个同学站成一排,要请最少的同学出列,使剩下的K位同学拍成合唱队型.
2.合唱队型是指,从左到右,身高依次上升,直到遇到身高最高的同学,再从右往左身高依次下降
3.我们的身高必须依次严格上升或者下降,如果有身高相等的同学站在一起,那么不形成合唱队型
4.你的任务是,已知N位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队型
5.注意:不允许改变队列元素的前后顺组
6.不要求最高同学左右人数必须相等
7.数据范围:n范围[1,3000]
8.输入描述:用例两行数据,第一行是同学的总数N,第二行是N位同学的身高,以空格隔开
9.输出描述:最少需要几位同学出列
二、解题思路
首先我们可以想一下,符合要求的合唱队型有哪些样式(定义n存储人数,定义int *heights存储每个人的身高)
160 180 160这种直接就是合唱队型
160 170 180这样应该也是符合标准的队型
180 170 160这样应该也符合标准
那么我们想一下,什么情况不符合标准呢?
第一种是两个身高相同的同学站在一起
160 180 180 160
一种是在身高上升的过程中,出现了身高较矮的同学(或者理解为身高上升的队型前有一名身高较高的同学因为160 180 160 和 150 180 160 都可以组成合唱队型)
160 150 180 160
一种是在身高下降的过程中,出现了身高较矮的同学(或者理解为身高下降的队型后有一名身高较高的同学因为160 180 150 和 160 180 160 都可以组成合唱队型)
160 180 150 160
因为我们的元素排列顺序不会改变
我们会发现,如果出现了使合唱队型不成立的同学的时候,他不会破坏我们原有的队型(或者说如果我们有一个160 180 180 160,我们只需要剔除一个180就可以组成合唱队型),我们只需要将他剔除就可以组成我们的合唱队型
那么如何计算影响我们合唱队型的人数呢?
首先我们要确保剔除的人数最小的话,那么我们参加合唱队型的人数就要最多
我们可以这样
定义一个数组increase[3000]
对于每名同学,我们需要计算出他的左边最多有多少按顺序,身高小于他的同学
比如我们的N是3,身高有160 180 160
对于第一名同学,他的左边没有同学,所以是0
对于第二名同学,他左边有一名同学,而且这名同学身高小于它,所以是1
对于第三名同学,他的左边有两名同学,身高都不小于它,所以是0
在定义一个decrease[3000]数组
然后我们再计算每名同学按顺序右边最多有多少身高小于他的同学,结果还是0 1 0
这个时候我们将两个数组的结果相加并保存在maxChorusLen[3000]数组中
这个时候我们就得到了,以每个同学为中心,能形成的最长的合唱队型
0 2 0
也就是说,以第一名同学为中心我们可以形成的合唱队型只有他自己
以第二名同学为中心我们形成的合唱队型有三个人(左边一人,右边一人)
以第三名同学为中心我们能形成的合唱队型也只有他自己
那么我们需要剔除的人数就是N-(2+1)(他自己)= 0
所以这个队型直接就是合格的队型
以这种方式我们来测试一下示例
186 186 150 200 160 130 197 200
| 186 | 186 | 150 | 200 | 160 | 130 | 197 | 200 | |
| increase | 0 | 0 | 0 | 1(186或者150的) | 1(150) | 0 | 2(比160高,160比另一个150高,所以197最多比两个人高) | 3(比197高,所以最多比3个人高) |
| decrease | 2 | 2 | 1(130) | 2(160\130) | 1(130) | 0 | 0 | 0 |
| maxChorusLen | 0+2=2 | 0+2=2 | 1 | 3 | 2 | 0 | 2 | 3 |
| N-(maxChorusLen+1) | 8-(2+1)=5 | 5 | 6 | 4 | 5 | 7 | 5 | 4 |
所以我们最少剔除人数是4,符合题意
三、具体步骤
使用的语言是C
#include <stdio.h>
#include <stdlib.h>
int main() {
int n;
scanf("%d", &n);
int* heights = (int *)malloc(n * sizeof(int));
for( int i = 0; i < n; i++){
scanf("%d", &heights[i]);
}
int increase[3000] = {0};
int decrease[3000] = {0};
for(int i = 1; i < n; i++){
for(int j = 0; j < i; j++){
if(heights[i] > heights[j] && increase[i] < increase[j] + 1){
increase[i] = increase[j] + 1;
}
}
}
for(int i = n - 2; i >= 0; i--){
for(int j = n - 1; j > i; j--){
if(heights[i] > heights[j] && decrease[i] < decrease[j] + 1){
decrease[i] = decrease[j] + 1;
}
}
}
int maxChorusLen[3000];
int max = 0;
for (int i = 0; i < 3000; i++){
maxChorusLen[i] = increase[i] + decrease[i];
if(maxChorusLen[i] > max) max = maxChorusLen[i];
}
printf("%d\n", n - max - 1);
return 0;
}原文地址：https://blog.csdn.net/bingw0114/article/details/143391934
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！