牛客网 HJ24 合唱队题目链接https://www.nowcoder.com/practice/6d9d69e3898f45169a441632b325c7b4一、原题完整陈述题目描述N位同学站成一排音乐老师要请其中的(N-K)位同学出列使得剩下的K位同学排成合唱队形。合唱队形定义K个人从左到右身高T1,T2...TKT_1,T_2...T_KT1​,T2​...TK​存在一个山顶位置i满足T1T2...TiT_1 T_2 ... T_iT1​T2​...Ti​然后TiTi1...TKT_i T_{i1} ...T_KTi​Ti1​...TK​也就是先严格递增到最高点后严格递减。要求不能改变同学原来的先后顺序。求最少需要几位同学出列才能排出合唱队形。数据范围1≤N≤30001 \le N \le 30001≤N≤3000输入描述第一行整数N同学总人数第二行N个整数空格隔开代表每位同学身高输出描述最少需要出列的同学数量示例输入8 186 186 150 200 160 130 197 200示例输出4解释保留4个人组成最长合唱队形总人数88-44所以最少4人出列。二、费曼学习法拆解破解思路讲给小白费曼核心用最简单大白话讲清楚假设听众不懂动态规划、不懂LIS。1. 翻译成人话理解需求一排同学站好顺序不能调换前后只能删掉一部分人。剩下的队伍必须满足左边一路越来越高到最高那个人之后一路越来越矮。我们目标保留尽可能多的人那么被踢出去的人就最少。关键点最高的那个人叫“山顶”。对每一个同学我们假设把他当成山顶看看① 他左边最多能保留多少人从左到右身高递增到他为止② 他右边最多能保留多少人从他向右身高递减那么以他为山顶总人数 左边最长递增人数 右边最长递减人数 -1减1是因为山顶同学被左右两边各统计了一次重复计算要扣掉1次。2. 拆解2个小问题最长递增子序列 LIS子序列不需要连续可以跳过中间元素但是顺序不能变。1dp_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)2dp_right[i]以第i个人作为开头往右边走最长严格递减子序列长度等价于数组反转求反转数组的最长递增子序列然后结果再反转回来。比如原数组[a,b,c,d]反转[d,c,b,a]求LIS再反转得到dp_right数组。3. 整体步骤模拟样例样例身高数组[186, 186, 150, 200, 160, 130, 197, 200]算出dp_left数组每个位置从左边到这个位置最长递增人数算出dp_right数组每个位置从这个位置向右最长递减人数遍历每一个i计算dp_left[i]dp_right[i]-1找出这个值全局最大值这就是最多可以留下来的人数最少出列人数 总人数N - 最多保留人数4. 坑点费曼自查容易卡壳的地方严格大于身高相等不算递增186后面再来186不能算上升子序列不是子数组不需要连续山顶可以是最左边整个队伍单调递减也可以是最右边整个队伍单调递增算法天然兼容多组输入ACM模式循环读取直到输入结束捕获EOFError。5. 复杂度分析两层循环O(n2)O(n^2)O(n2)题目n最大30003000*3000900万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总同学人数nint(input())# 读取第二行分割字符串转成整数列表保存所有人身高heightslist(map(int,input().split()))# dp_left[i]从左向右以i结尾最长严格递增子序列长度dp_leftget_lis(heights)# 把身高数组反转求反转数组的最长递增子序列# 反转数组的LIS等价于原数组从右向左的递增 原数组向右的递减reversed_heightsheights[::-1]reversed_dpget_lis(reversed_heights)# 再把dp反转回来得到dp_right# dp_right[i]以i为起点向右最长严格递减子序列长度dp_rightreversed_dp[::-1]# 变量max_keep记录可以保留的最多人数初始0max_keep0# 遍历每一个位置i假设i是山顶最高点foriinrange(n):# dp_left[i]左上升人数 dp_right[i]右下降人数# -1 山顶i被左右两边重复计算1次减去重复currentdp_left[i]dp_right[i]-1# 更新最大保留人数ifcurrentmax_keep:max_keepcurrent# 最少出列人数 总人数 - 能留下来的最多人数out_numn-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生产线质量时序筛选采集产品检测指标寻找最长先升高后降低的子序列定位工艺参数的最高点。五、费曼复盘总结复述一遍巩固这道题本质寻找最长“先严格上升后严格下降”的子序列。动态规划求正向LIS左边上升数组反转求LIS再反转得到右侧递减序列每一个点作为山顶左右相加减1找到最大值最多保留人数总人数减去最大保留人数就是最少出列人数。核心知识点动态规划DP、最长递增子序列LIS、子序列非连续、ACM多组输入EOF捕获。拓展可选优化上面代码是O(n²)基础DP机考写这个最稳不容易写错如果n更大例如1e5要用二分优化LIS复杂度O(n log n)。如果你想要我可以继续给你二分优化O(n log n)版本代码逐行注释手动演算完整dp_left dp_right数组全过程边界测试用例清单全部递增、全部递减、全部数字相同