【NOIP提高组】合唱队形

- - C语言
  - Java

💐The Begin💐点点关注，收藏不迷路💐

N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，则他们的身高满足T1<…Ti+1>…>TK(1<=i<=K)。
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

输入

输入的第一行是一个整数N(2<=N<=100)，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。

输出

输出文一行，这一行只包含一个整数，就是最少需要几位同学出列。

样例输入

8
186 186 150 200 160 130 197 220

样例输出

提示

【数据规模】
对于50％的数据，保证有n<=20；
对于全部的数据，保证有n<=100。

C语言

#include <stdio.h>#define MAX_STUDENTS 105int main() {int heights[MAX_STUDENTS]; // 存储同学身高的数组，简称heightsint leftIncreasing[MAX_STUDENTS]; // 记录从左往右每个位置左边递增序列长度，简称leftIncreasingint rightDecreasing[MAX_STUDENTS]; // 记录从右往左每个位置右边递减序列长度，简称rightDecreasingint chorusSizes[MAX_STUDENTS]; // 记录每个位置左右序列合并后的合唱队形大小，简称chorusSizesint numStudents; // 同学的总数，简称numStudentsint maxChorusSize; // 最大的合唱队形大小，简称maxChorusSize// 读取同学总数scanf("%d", &numStudents);// 读取每位同学的身高，并初始化相关数组for (int i = 1; i <= numStudents; i++) {scanf("%d", &heights[i]); // 读取第i位同学的身高并存入heights数组，简称i为同学序号leftIncreasing[i] = 1;rightDecreasing[i] = 1;}// 从右往左，按左高右低顺序找出每一个位置右边有几个从高到低的数（包括自己）for (int i = numStudents - 1; i >= 1; i--) {for (int j = i + 1; j <= numStudents; j++) {if (heights[i] > heights[j] && leftIncreasing[i] <= leftIncreasing[j] + 1) {leftIncreasing[i] = leftIncreasing[j] + 1;}}}// 从左往右，按左低右高顺序找出每一个位置左边有几个从低到高的数（包括自己）for (int i = 2; i <= numStudents; i++) {for (int j = 1; j < i; j++) {if (heights[i] > heights[j] && rightDecreasing[i] <= rightDecreasing[j] + 1) {rightDecreasing[i] = rightDecreasing[j] + 1;}}}maxChorusSize = 0;// 计算每个位置左右序列合并后的合唱队形大小，并找出最大的合唱队形大小for (int i = 1; i <= numStudents; i++) {chorusSizes[i] = leftIncreasing[i] + rightDecreasing[i] - 1;// 注意！自己加了两次要 -1if (chorusSizes[i] > maxChorusSize) {maxChorusSize = chorusSizes[i];}}// 输出最少需要出列的同学数printf("%d\n", numStudents - maxChorusSize);return 0;
}

Java

import java.util.Scanner;public class Main {public static final int MAX_STUDENTS = 105;public static void main(String[] args) {int[] heights = new int[MAX_STUDENTS]; // 存储同学身高的数组，简称heightsint[] leftIncreasing = new int[MAX_STUDENTS]; // 记录从左往右每个位置左边递增序列长度，简称leftIncreasingint[] rightDecreasing = new int[MAX_STUDENTS]; // 记录从右往左每个位置右边递减序列长度，简称rightDecreasingint[] chorusSizes = new int[MAX_STUDENTS]; // 记录每个位置左右序列合并后的合唱队形大小，简称chorusSizesint numStudents; // 同学的总数，简称numStudentsint maxChorusSize; // 最大的合唱队形大小，简称maxChorusSizeScanner scanner = new Scanner(System.in);// 读取同学总数numStudents = scanner.nextInt();// 读取每位同学的身高，并初始化相关数组for (int i = 1; i <= numStudents; i++) {heights[i] = scanner.nextInt(); // 读取第i位同学的身高并存入heights数组，简称i为同学序号leftIncreasing[i] = 1;rightDecreasing[i] = 1;}// 从右往左，按左高右低顺序找出每一个位置右边有几个从高到低的数（包括自己）for (int i = numStudents - 1; i >= 1; i--) {for (int j = i + 1; j <= numStudents; j++) {if (heights[i] > heights[j] && leftIncreasing[i] <= leftIncreasing[j] + 1) {leftIncreasing[i] = leftIncreasing[j] + 1;}}}// 从左往右，按左低右高顺序找出每一个位置左边有几个从低到高的数（包括自己）for (int i = 2; i <= numStudents; i++) {for (int j = 1; j < i; j++) {if (heights[i] > heights[j] && rightDecreasing[i] <= rightDecreasing[j] + 1) {rightDecreasing[i] = rightDecreasing[j] + 1;}}}maxChorusSize = 0;// 计算每个位置左右序列合并后的合唱队形大小，并找出最大的合唱队形大小for (int i = 1; i <= numStudents; i++) {chorusSizes[i] = leftIncreasing[i] + rightDecreasing[i] - 1;// 注意！自己加了两次要 -1if (chorusSizes[i] > maxChorusSize) {maxChorusSize = chorusSizes[i];}}// 输出最少需要出列的同学数System.out.println(numStudents - maxChorusSize);scanner.close();}
}