首页 > 试题广场 >

合唱队

[编程题]合唱队

热度指数：318706 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

N 位同学站成一排，音乐老师要请最少的同学出列，使得剩下的 K 位同学排成合唱队形。

设 $K$ 位同学从左到右依次编号为 1，2…，K ，他们的身高分别为 $T_1,T_2,…,T_K$ ，若存在 $i(1\lt i\lt K)$ 使得 $T_1<T_2<......<T_{i-1}<T_i$ 且 $T_i>T_{i+1}>......>T_K$ ，则称这 $K$ 名同学排成了合唱队形。

通俗来说，能找到一个同学，他的两边的同学身高都依次严格降低的队形就是合唱队形。

例子：

123 124 125 123 121 是一个合唱队形

123 123 124 122不是合唱队形，因为前两名同学身高相等，不符合要求

123 122 121 122不是合唱队形，因为找不到一个同学，他的两侧同学身高递减。

你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

注意：不允许改变队列元素的先后顺序 且 不要求最高同学左右人数必须相等

输入描述:

用例两行数据，第一行是同学的总数 N ，第二行是 N 位同学的身高h[i]，以空格隔开

数据范围： $1 \le n \le 3000 \$ ， $0<=h[i]<=1e5$

输出描述:

最少需要几位同学出列

示例1

输入

8
186 186 150 200 160 130 197 200

输出

说明

由于不允许改变队列元素的先后顺序，所以最终剩下的队列应该为186 200 160 130或150 200 160 130

算法知识视频讲解

bettermin

发表于 2020-04-18 17:15:17

题目描述计算最少出列多少位同学，使得剩下的同学排成合唱队形说明： N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，则他们的身高满足存在i（1& 展开全文

牛客320475094号

发表于 2020-05-16 22:29:03

先找到每一个位置i左侧的最长上升子序列长度numL[i]：每一个位置左侧最长子序列长度等于其左侧比它小的所有位置的最长子序列长度中的最大值+1再找到每一个位置i右侧的最长下降子序列长度numR[i]：每一个位置右侧最长子序列长度等于其右侧比它小的所有位置的最长子序列长度中的最大值+1然后求出所有位置展开全文

代码界的小白

发表于 2021-12-02 14:19:22

题目主要信息 1、给出n个同学的身高，在不改变所有人的相对位置的情况下从中剔除几位，使得剩下的k*位同学的身高排序是形如：T1<T2<......<Ti-1Ti+1>......>TK 。 2、不允许改变队列元素的先后顺序且不要求最高同学左右人数必须相等 3、求最少展开全文

明刘

发表于 2021-11-08 21:43:27

#合唱队# 此题是最长递增子序列的变体，基本思路是对原序列从左到右和从右到左分别求出到每个元素的最长递增子序列的长度。例如，原序列为长度为N的序列[8,20,12,15,10,9]，从左至右的到序列里每个元素的最长递增子序列为l1=[1,2,2,3,2,2]，从右至左为l2=[1,4,3,3,2,1 展开全文

那年庐州月光

发表于 2021-07-05 20:19:58

这题抛开场景，核心问题是最长递增子序列，可以参考leetcode 最长递增子序列来理解。总的来说，就是自左向右求出最长递增子序列的最优值dp数组，自右向左求出最长递减子序列的最优值dp数组，两者对位相加-1，其中的最大值，就是整个合唱队留在场上的人数的最大值，因此也就是出列的最小值。 dp的这部展开全文

emoo

发表于 2022-02-01 03:25:05

动态规划二分搜索法 /*最长上升子序列问题中间最高，向两边逐渐减小（相等也不行）。不要求最高的同学左右人数必须相等。不允许改变队列元素的先后顺序，也就是说，只能剔除不能排序。计算最少需要出列几名同学满足以上要求，也就是说，剔除某些同学，剩下的队列自然而然的满足要求（1）计算出每个展开全文

江帆-

发表于 2021-10-31 19:21:32

动态规划这里跟以往不一样的是，需要注意一下上升子序列的定义，这里的子序列可以是间断的，这就加大了这个问题的难度。我们用动态规划来解决这个问题，定义数组dp，长度与输入数组nums保持一致，dp[i]所代表的含义是以nums[i]结尾的所有上升子序列的最大长度。例如在数组[1, 7, 2, 3, 展开全文