牛客网 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_iT1T2...Ti然后TiTi1...TKT_i T_{i1} ...T_KTiTi1...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数组全过程边界测试用例清单全部递增、全部递减、全部数字相同
企业数字化 ERP 产品动态
相关推荐
OV5640分辨率切换踩坑：从VGA到1080p/720p寄存器配置实战解析 /* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/24 4:23:28
人声分离工具怎么选 选择人声分离工具，核心是匹配你的分离目标和素材条件——不同工具对复杂混音频谱的分离精度不同，对原始素材的质量要求也有差异。你可以先明确自己需要保留什么、分离后用来做什么，再根据素材质量验证分离效果，最后选择符合精度要… · 2026/9/24 4:23:21
鼎芯微碳化硅控制IC：重构电源架构的工程实践指南 /* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/24 4:23:21
一读就懂！B端响应式设计的新手扫盲 兰亭妙微UI设计公司：最近重新更新一下 B 端响应式相关的内容，帮助已经初步掌握的同学重新巩固，还没学会的同学快速入门。
响应式的适配对象
响应式是一种网页前端技术，让网页可以根据分辨率、设备的变更，自动调整样式… · 2026/9/24 5:15:28
学生宿舍楼综合布线实战设计：952个信息点全链路交付指南 /* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/24 5:15:28
FormConsumer 表单响应消费者：Vue 3 / Vue 2 下的响应式 UI 订阅组件 前端UI组件 【免费下载链接】formily 📱🚀 🧩 Cross Device & High Performance Normal Form/Dynamic(JSON Schema) Form/Form Builder -- Support React/React Native/Vue 2/Vue 3 项目地址： https://gitcode.com/gh_mirrors… · 2026/9/24 5:15:21
OpenLayers v3.16.0 版本解析：核心新特性、升级要点与源码实现解读 前端GIS数据可视化 【免费下载链接】openlayers OpenLayers 项目地址： https://gitcode.com/gh_mirrors/op/openlayers 点击查看 免费下载 本文以 OpenLayers 仓库中的 changelog/v3.16.0.md 为主体，结合仓库源码对 v3.16.0 引入的新 API、行为变更与升… · 2026/9/24 5:15:09
Android 一套代码扛几十种坐标系？投影类型到 proj 字符串翻译 业务层面向对象，底层引擎只认 proj 字符串。中间类型映射表，藏着不少反直觉的坑。前言
做坐标转换功能的工程师，大概率都遇到过这种割裂：业务层想要"面向对象"——一个坐标系就是一个对象，里面有椭球、投影类… · 2026/9/24 5:15:09
SemIf 的 Apple Silicon 原生 MLX 后端：安装、量化、缓存复用与证据复现实战指南 【免费下载链接】SemIf-OpenJev Semantic ifs from open models, on a 3090 at home. Independent; not affiliated with Jev or TypeSafe. 项目地址： https://gitcode.com/gh_mirrors/op/SemIf-OpenJev 点击查看 免费下载 SemIf（语义决策开源基线&… · 2026/9/24 5:15:03
基于YOLOv8的渔船作业监控系统：从环境搭建到边缘部署全流程 简介：这是一套面向计算机、人工智能、自动化等专业学生与教师的毕业设计级项目资源，围绕YOLOv8实现渔船作业监控系统，可用于毕设、课程设计、大作业或项目立项演示。压缩包共97个文件，约24.21MB，以70个Python源码文件为… · 2026/9/24 0:00:13
1D-CNN时间序列建模实战：从Conv1d原理到工业落地 简介：面向时间序列数据建模的一维卷积神经网络完整实现，适合深度学习入门者及需要快速验证时序模型的研究者，能够从音频、文本、传感器或股价等序列中挖掘局部特征与时间依赖。压缩包体积很小，只有3KB，内含3个Python脚… · 2026/9/24 0:00:26
柔软的L：汉语语流中被忽视的舌肌张力控制 1. 这个“L”不是字母表里的L，而是舌尖上的L最近在几个方言群和语音教学社群里，反复看到有人发一句：“也说字母L：柔软的长舌”。初看以为是英语发音课笔记，点开才发现全是方言爱好者、播音系学生、语言康复师甚至戏曲演… · 2026/9/24 0:00:44
