小美的数组删除
美团 2024-08-10 后端笔试编程题（编程题第 2 题）
题目描述
小美有一个长度为 n 的数组 a，她可以对数组进行如下操作：
- 删除第一个元素 a[1]，同时数组长度减一，花费为 x；
- 删除整个数组，花费为
k * MEX(a)，其中MEX(a)表示 a 中未出现过的 最小非负整数（例如[0,1,2,4]的 MEX 为 3）。
小美想知道将数组全部清空的最小代价。
输入格式
第一行一个整数 T，代表数据组数。 每组数据：
- 第一行三个正整数 n、k、x（1 ≤ n ≤ 2×10⁵，1 ≤ k, x ≤ 10⁹）；
- 第二行 n 个整数 a[i]（0 ≤ a[i] ≤ n）。
保证所有数据组的 n 之和不超过 2×10⁵。
输出格式
对每组数据，在一行输出一个整数，表示清空数组的最小花费。
示例
示例 1
输入：
1
6 3 3
4 5 2 3 1 0
输出：
15
说明：
不删元素直接整段删除，MEX{4,5,2,3,1,0} = 6，花费 18；
先删掉第一个元素 4，再整段删除，MEX{5,2,3,1,0} = 4，花费 3 + 12 = 15，最省。
解题思路
第一步：状态定义
操作只会发生在「数组的前缀被删掉之后」—— 剩下的永远是原数组的一个后缀。
设 f[i] 表示删光后缀 a[i..n-1]（下标 0 起）的最小花费。
第二步：转移
面对后缀 a[i..n-1]，只有两种「下一步」：
f[i] = min( x + f[i+1], # 先单独删掉 a[i]
k * MEX(a[i..n-1]) ) # 直接整段删除
- 单独删
a[i]后，问题变成更短的后缀，所以是x + f[i+1]； - 或者直接一步删掉整段，代价是当前后缀的 MEX 乘以 k。
边界 f[n] = 0（空数组不用花钱）。答案就是 f[0]。
第三步：怎么快速求每个后缀的 MEX
如果每个后缀都重新算 MEX，总复杂度 O(n²)，会超时。
关键观察：i 从 n-1 递减到 0 时，后缀是不断变大的
（每次只多一个元素 a[i]）。因此 MEX 只会单调不减 ——
用一个指针 mex 边走边扩即可：
- 加入
a[i]后，如果它正好等于当前mex，就让mex一直自增， 直到遇到一个「没在后缀里出现过」的值。
每个值最多让 mex 前进一步，所以整个循环是 O(n) 的。
完整代码实现
算法可视化 · 逐帧回放这道题的代码70 帧 · 录制输入
import sys
def solve() -> None:
"""后缀 DP + 单调递增的 MEX 指针"""
data = sys.stdin.read().split()
if not data:
return
idx = 0
t = int(data[idx]); idx += 1
out = []
for _ in range(t):
n = int(data[idx]); k = int(data[idx + 1]); x = int(data[idx + 2]); idx += 3
a = [int(v) for v in data[idx:idx + n]]; idx += n
present = [False] * (n + 2)
mex = 0
f_next = 0 # f[n]
for i in range(n - 1, -1, -1):
v = a[i]
if v < len(present):
present[v] = True
while mex < len(present) and present[mex]:
mex += 1
f_cur = min(x + f_next, k * mex)
f_next = f_cur
out.append(str(f_next))
sys.stdout.write("\n".join(out) + "\n")
if __name__ == "__main__":
solve()
示例推演
a = [4,5,2,3,1,0]，k = 3，x = 3，从后往前算：
| i | 后缀 | MEX | 单独删 (x+f[i+1]) | 整段删 (k·MEX) | f[i] |
|---|---|---|---|---|---|
| 6 | 空 | — | — | — | 0 |
| 5 | [0] | 1 | 3 + 0 = 3 | 3 | 3 |
| 4 | [1,0] | 2 | 3 + 3 = 6 | 6 | 6 |
| 3 | [3,1,0] | 2 | 3 + 6 = 9 | 6 | 6 |
| 2 | [2,3,1,0] | 4 | 3 + 6 = 9 | 12 | 9 |
| 1 | [5,2,3,1,0] | 4 | 3 + 9 = 12 | 12 | 12 |
| 0 | [4,5,2,3,1,0] | 6 | 3 + 12 = 15 | 18 | 15 |
答案 f[0] = 15，与样例一致。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 每个后缀重算 MEX | O(n²) | O(n) | 超时 |
| 后缀 DP + 单调 MEX | O(n) | O(n) | 推荐 |
易错点总结
1. 每一轮都重新求 MEX
这是最容易踩的性能坑。后缀是逐步变大的，MEX 只会增大， 用一个指针维护即可，不要每次重算。
2. 把 MEX 当成「最大值 + 1」
MEX 是「未出现的最小非负整数」，与最大值无关。
例如 [0,1,2,4] 的 MEX 是 3，而不是 5。
3. 只考虑「整段删除」或「只删单个」
两种操作要组合比较最小值；只选一种会漏掉更优解。
4. 多组数据的清理
present 数组和 mex 每组都要重新初始化，不要跨组复用。
扩展思考
- 若「删除整个数组」的代价改成与元素个数有关（如
k * 长度）， 转移会相应变化。 - 「动态维护 MEX」是常见技巧：只要是单向只会变大的场景， 都可以用单调指针把均摊复杂度降到 O(1)。