华为机试】HJ24 合唱队"/>
【java华为机试】HJ24 合唱队
描述
计算最少出列多少位同学,使得剩下的同学排成合唱队形
说明:
N 位同学站成一排,音乐老师要请其中的 (N - K) 位同学出列,使得剩下的 K 位同学排成合唱队形。
合唱队形是指这样的一种队形:设K位同学从左到右依次编号为 1,2…,K ,他们的身高分别为 T1,T2,…,TK , 则他们的身高满足存在 i (1<=i<=K) 使得 T1<T2<......<Ti-1<Ti>Ti+1>......>TK 。
你的任务是,已知所有N位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。
注意:不允许改变队列元素的先后顺序 且 不要求最高同学左右人数必须相等
数据范围: 1 \le n \le 3000 \1≤n≤3000
输入描述:
用例两行数据,第一行是同学的总数 N ,第二行是 N 位同学的身高,以空格隔开
输出描述:
最少需要几位同学出列
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNextInt()) {int num = sc.nextInt();int[] arr = new int[num];for (int i = 0; i < num; i++) {arr[i] = sc.nextInt();}int[] arrL = new int[num];// 计算左边比arr[i]大的情况,并对arrL[i]进行累加,算出每个值左边比自己大的数。for (int i = 0; i < num; i++) {arrL[i] = 0;for (int j = 0; j < i; j++) {if (arr[i] > arr[j]) {// 如果知道arr[j]比左边几个人高,那arr[i]比arr[j]大,那就只需要加1就可以了。arrL[i] = Math.max(arrL[i], arrL[j] + 1);}}}int[] arrR = new int[num];// 计算右边比arr[i]大的情况,并对arrR[i]进行累加,算出每个值右边比自己大的数。for (int i = num - 1; i >= 0; i--) {arrR[i] = 0;for (int j = num - 1; j > i; j--) {if (arr[i] > arr[j]) {// 如果知道arr[j]比右边几个人高,那arr[i]比arr[j]大,那就只需要加1就可以了。arrR[i] = Math.max(arrR[i], arrR[j] + 1);}}}// 计算 arrL[i]+arrR[i]+1 的值,然后对所有这个值进行对比,挑选出最大的。int maxValue = 0;for (int i = 0; i < num; i++) {maxValue = Math.max(maxValue, arrL[i] + arrR[i] + 1);}// 队伍中总人数,减去maxValue,就是最少需要出列的人数。System.out.println(num - maxValue);}}}
输入:
8 186 186 150 200 160 130 197 200
输出:
4
更多推荐
【java华为机试】HJ24 合唱队
发布评论