首页 > 试题广场 >

合唱队

[编程题]合唱队

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

$\hspace{15pt}$ 音乐课上，老师将 $n$ 位同学排成一排。老师希望在不改变同学相对位置的前提下，从队伍中选出最少数量的同学，使得剩下的同学排成合唱队形。
$\hspace{15pt}$ 记合唱队形中一共有 $k$ 位同学，记编号为 $1,2,\dots,k$ ，第 $i$ 个人的身高为 $h_i$ 。要求：存在一位同学编号为 $i \left(1 < i < k\right)$ ，使得 $h_1,h_2,\dots,h_{i-1}$ 严格递增，且 $h_{i+1},h_{i+2},\dots,h_k$ 严格递减；更具体地，合唱队形呈 $h_1 < h_2 < \cdots < h_{i-1} < h_i$ 、 $h_i > h_{i+1} > \cdots > h_k$ 。
$\hspace{15pt}$ 你能帮助老师计算，最少需要出列多少位同学，才能使得剩下的同学排成合唱队形？

输入描述:

第一行输入一个整数  代表同学数量。
第二行输入  个整数  代表每一位同学的身高。

输出描述:

输出一个整数，代表最少需要出列的同学数量。

示例1

输入

8
186 186 150 200 160 130 197 200

输出

说明

在这个样例中，有且仅有两种出列方式，剩下的同学分别为  和  。

算法知识视频讲解

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, 展开全文