HJ24. 合唱队
题目描述
N 位同学站成一排，音乐老师要请其中的 (N-K) 位同学出列，使得剩下的 K 位同学排成合唱队形。合唱队形要求：从左到右先递增后递减，即存在一个"最高点"。
求最少需要出列多少人。
输入格式
- 第 1 行：整数 N（同学人数）
- 第 2 行：N 个正整数，表示每个同学的身高
输出格式
一个整数，表示最少需要出列的人数。
示例
示例 1
输入：
8
186 186 150 200 160 130 197 200
输出：
4
说明： 保留 186、200、197、200（最高点在 200 处，左侧 186<200、右侧 197<200），需出列 4 人。
示例 2
输入：
6
2 1 5 3 4 2
输出：
2
解题思路
第一步：理解问题本质
合唱队形 = "先升后降"，最高点 k 处要求：左侧 [0..k] 严格递增、右侧 [k..N-1] 严格递减。我们希望保留尽量多的人，等价于找到满足该条件的最长序列，再用总人数减它得到最少出列人数。
第二步：暴力解法
枚举所有子序列，判断是否先升后降，取最长。2^N 种可能，指数级，不可行。
第三步：转为最长递增子序列（LIS）
关键观察：对于每个位置 i 作为最高点，它能形成的合唱队形长度为：
- 左侧从
0到i的最长递增子序列长度（严格递增） - 右侧从
i到N-1的最长递减子序列长度（即反向数组上的 LIS）
两者相加再减 1（位置 i 被算了两次），就是 i 作为最高点时可保留的最多人数。
第四步：最优解法（两次 LIS）
用经典 O(N²) LIS 计算：
inc[i]：以位置 i 结尾的最长递增子序列长度dec[i]：以位置 i 结尾的最长递增子序列长度（对反转数组求 LIS 后再反转）
inc = lis_len(heights)
dec = lis_len(heights[::-1])[::-1]
max_keep = max(inc[i] + dec[i] - 1 for i in range(N))
print(N - max_keep)
完整代码实现
算法可视化 · 逐帧回放这道题的代码194 帧 · 录制输入
import sys
def lis_len(seq):
"""返回以每个位置结尾的最长递增子序列长度列表"""
n = len(seq)
dp = [1] * n
for i in range(n):
for j in range(i):
if seq[j] < seq[i]: # 严格递增
dp[i] = max(dp[i], dp[j] + 1)
return dp
def solve():
data = sys.stdin.buffer.read().split()
n = int(data[0])
heights = list(map(int, data[1:1 + n]))
inc = lis_len(heights)
dec = lis_len(heights[::-1])[::-1]
max_keep = max(inc[i] + dec[i] - 1 for i in range(n))
print(n - max_keep)
if __name__ == "__main__":
solve()
示例推演
以示例 1 的 186 186 150 200 160 130 197 200 为例：
从左到右 LIS（inc）：
| 位置 | 身高 | inc |
|---|---|---|
| 0 | 186 | 1 |
| 1 | 186 | 1 |
| 2 | 150 | 1 |
| 3 | 200 | 2 |
| 4 | 160 | 2 |
| 5 | 130 | 1 |
| 6 | 197 | 3 |
| 7 | 200 | 4 |
从右到左 LIS（dec）：
| 位置 | 身高 | dec |
|---|---|---|
| 0 | 186 | 3 |
| 1 | 186 | 3 |
| 2 | 150 | 2 |
| 3 | 200 | 3 |
| 4 | 160 | 2 |
| 5 | 130 | 1 |
| 6 | 197 | 1 |
| 7 | 200 | 1 |
计算每个位置作为最高点时最多可保留的人数 inc[i] + dec[i] - 1：
| 位置 | inc | dec | 保留人数 |
|---|---|---|---|
| 0 | 1 | 3 | 3 |
| 1 | 1 | 3 | 3 |
| 2 | 1 | 2 | 2 |
| 3 | 2 | 3 | 4 |
| 4 | 2 | 2 | 3 |
| 5 | 1 | 1 | 1 |
| 6 | 3 | 1 | 3 |
| 7 | 4 | 1 | 4 |
结果：最多保留 max = 4 人，最少出列 = N - max = 8 - 4 = 4。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 暴力枚举 | O(2^N) | O(N) | 指数级，不可行 |
| 两次 LIS | O(N²) | O(N) | N ≤ 3000，可接受 |
N 为同学人数
易错点总结
1. 忘记"严格递增/递减"
题目要求严格递增递减，seq[j] < seq[i] 不能写成 <=，否则相邻相等的身高会被错误保留。
2. dec 数组方向写错
dec 是对反转数组求 LIS 后再反转，最容易写错。先反转、算完、再反转，保证 dec[i] 与 inc[i] 下标对齐。
3. 最高点重复计数
inc[i] + dec[i] 把位置 i 数了两次，必须减 1。
扩展思考
- 本题 N 较小用 O(N²) 即可；若 N 达到 1e5，可用「贪心 + 二分」将 LIS 优化到 O(N log N)。
- 同类"先升后降"问题都可以套用"正反两次 LIS"模型，例如求山峰数组的最长子序列。