企业官网建设流程全解析

牛客网 HJ24 合唱队

题目链接：https://www.nowcoder.com/practice/6d9d69e3898f45169a441632b325c7b4

一、原题完整陈述

题目描述

N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。
合唱队形定义：K个人从左到右身高T1,T2...TKT_1,T_2...T_KT1​,T2​...TK​，存在一个山顶位置i，满足：
T1<T2<...<TiT_1 < T_2 < ... < T_iT1​<T2​<...<Ti​，然后Ti>Ti+1>...>TKT_i > T_{i+1} > ...>T_KTi​>Ti+1​>...>TK​
也就是先严格递增，到最高点后严格递减。
要求：不能改变同学原来的先后顺序。求最少需要几位同学出列，才能排出合唱队形。

数据范围：1≤N≤30001 \le N \le 30001≤N≤3000

输入描述

• 第一行：整数N，同学总人数
• 第二行：N个整数，空格隔开，代表每位同学身高

输出描述

最少需要出列的同学数量

示例输入

8 186 186 150 200 160 130 197 200

示例输出

4

解释：保留4个人组成最长合唱队形，总人数8，8-4=4，所以最少4人出列。

二、费曼学习法拆解破解思路（讲给小白）

费曼核心：用最简单大白话讲清楚，假设听众不懂动态规划、不懂LIS。

1. 翻译成人话理解需求

一排同学站好顺序，不能调换前后，只能删掉一部分人。
剩下的队伍必须满足：左边一路越来越高，到最高那个人之后，一路越来越矮。
我们目标：保留尽可能多的人，那么被踢出去的人就最少。

关键点：最高的那个人叫“山顶”。
对每一个同学，我们假设把他当成山顶，看看：
① 他左边，最多能保留多少人（从左到右身高递增，到他为止）
② 他右边，最多能保留多少人（从他向右身高递减）
那么以他为山顶总人数 = 左边最长递增人数 + 右边最长递减人数 -1
减1是因为山顶同学被左右两边各统计了一次，重复计算，要扣掉1次。

2. 拆解2个小问题（最长递增子序列 LIS）

子序列：不需要连续，可以跳过中间元素，但是顺序不能变。

1）dp_left[i]：以第i个人作为结尾，从左边过来的最长严格递增子序列长度
初始所有人dp_left[i]=1，自己单独一个人。
遍历i，看i前面所有j，如果height[j] < height[i]，就更新dp_left[i] = max(dp_left[i], dp_left[j]+1)

2）dp_right[i]：以第i个人作为开头，往右边走最长严格递减子序列长度
等价于：数组反转，求反转数组的最长递增子序列，然后结果再反转回来。
比如原数组[a,b,c,d]反转[d,c,b,a]求LIS，再反转得到dp_right数组。

3. 整体步骤模拟样例

样例身高数组：[186, 186, 150, 200, 160, 130, 197, 200]

1. 算出dp_left数组：每个位置，从左边到这个位置最长递增人数
2. 算出dp_right数组：每个位置，从这个位置向右最长递减人数
3. 遍历每一个i，计算dp_left[i]+dp_right[i]-1，找出这个值全局最大值（这就是最多可以留下来的人数）
4. 最少出列人数 = 总人数N - 最多保留人数

4. 坑点（费曼自查，容易卡壳的地方）

1. 严格大于，身高相等不算递增，186后面再来186不能算上升；
2. 子序列不是子数组，不需要连续；
3. 山顶可以是最左边（整个队伍单调递减），也可以是最右边（整个队伍单调递增），算法天然兼容；
4. 多组输入，ACM模式，循环读取直到输入结束，捕获EOFError。

5. 复杂度分析

两层循环，O(n2)O(n^2)O(n2)，题目n最大3000，3000*3000=900万，Python完全跑得动，机考首选简单DP写法，不用进阶二分优化。

三、Python完整代码，每行详细注释

# HJ24 合唱队 牛客华为机试题# ACM模式，支持多组输入，动态规划求最长先增后减子序列defget_lis(arr):""" 自定义函数：输入数组arr，返回dp数组 dp[i]代表：以arr[i]作为结尾的【最长严格递增子序列长度】 """# 初始化dp数组，每个元素初始值=1，最少自己单独1个人dp=[1]*len(arr)# i遍历数组每一个位置，i是当前结尾位置foriinrange(len(arr)):# j遍历i前面所有元素，j < iforjinrange(i):# 如果前面j位置身高 < 当前i身高，可以接在j的递增序列后面ifarr[j]<arr[i]:# 取原来dp[i] 和 dp[j]+1 两者中更大的值更新dp[i]dp[i]=max(dp[i],dp[j]+1)# 返回整个dp数组returndpdefmain():# 无限循环，处理牛客OJ多组测试样例whileTrue:try:# 读取第一行，转为整数n：总同学人数n=int(input())# 读取第二行，分割字符串转成整数列表，保存所有人身高heights=list(map(int,input().split()))# dp_left[i]：从左向右，以i结尾最长严格递增子序列长度dp_left=get_lis(heights)# 把身高数组反转，求反转数组的最长递增子序列# 反转数组的LIS等价于原数组从右向左的递增 = 原数组向右的递减reversed_heights=heights[::-1]reversed_dp=get_lis(reversed_heights)# 再把dp反转回来，得到dp_right# dp_right[i]：以i为起点，向右最长严格递减子序列长度dp_right=reversed_dp[::-1]# 变量max_keep：记录可以保留的最多人数，初始0max_keep=0# 遍历每一个位置i，假设i是山顶最高点foriinrange(n):# dp_left[i]左上升人数 + dp_right[i]右下降人数# -1 山顶i被左右两边重复计算1次，减去重复current=dp_left[i]+dp_right[i]-1# 更新最大保留人数ifcurrent>max_keep:max_keep=current# 最少出列人数 = 总人数 - 能留下来的最多人数out_num=n-max_keep# 输出结果print(out_num)# 捕获EOFError，读到输入末尾，没有更多输入，跳出循环结束程序exceptEOFError:break# 程序入口，运行主函数if__name__=="__main__":main()

运行样例测试

输入：

8 186 186 150 200 160 130 197 200

输出：

4

四、应用场景举例

场景1：舞台队形自动编排（原题场景）

晚会上台人员固定顺序，只能删除部分人，要求队形中间最高，向两边逐步降低。程序快速算出最少淘汰人数，不用人工挨个试。

场景2：股票走势分析

给定一段时间股价序列，寻找一段先上涨后下跌的最长行情段。
dp_left：到每一天为止最长上涨子序列；dp_right：从当天开始最长下跌子序列。用来找“顶部拐点”，识别牛市转熊市的最长行情区间。

场景3：信号峰值检测

传感器采集时序数据，在不改变原始时序顺序前提下，寻找最长先上升后下降波形，用来识别脉冲峰值。

场景4：商品销量时序筛选

电商一段时间每日销量，寻找最长一段：前期销量持续增长，到达峰值后持续下滑的周期，分析爆款生命周期。

场景5：生产线质量时序筛选

采集产品检测指标，寻找最长先升高后降低的子序列，定位工艺参数的最高点。

五、费曼复盘总结（复述一遍巩固）

这道题本质：寻找最长“先严格上升，后严格下降”的子序列。

1. 动态规划求正向LIS（左边上升）
2. 数组反转求LIS再反转，得到右侧递减序列
3. 每一个点作为山顶，左右相加减1，找到最大值（最多保留人数）
4. 总人数减去最大保留人数，就是最少出列人数。

核心知识点：动态规划DP、最长递增子序列LIS、子序列（非连续）、ACM多组输入EOF捕获。

拓展可选优化

上面代码是O(n²)基础DP，机考写这个最稳不容易写错；
如果n更大（例如1e5），要用二分优化LIS，复杂度O(n log n)。

如果你想要，我可以继续给你：

1. 二分优化O(n log n)版本代码+逐行注释
2. 手动演算完整dp_left dp_right数组全过程
3. 边界测试用例清单（全部递增、全部递减、全部数字相同）