前几天整理春招笔试真题某游戏大厂3月14日的第二题“乱翘的数组hard”给我印象很深。名字听着像模拟题实际是一道披着数组外壳的经典单调化问题给你一个长度为n的整数数组允许把任意一个数改成任意整数每次修改的代价是修改前后数值差的绝对值最后要求整个数组变成非递减问最小总代价。这道题把离散化DP和反悔贪心两个重要考点串在一起同时标题里明确要了Java、C、Python三种解析所以我把完整的题意拆解、思路演变、正确性解释、三种语言提交代码以及一套本地对拍方法都整理出来。建议先想清楚贪心为什么错再看堆解法不然很容易背下代码换一组数据就WA。1. 题目回顾与题意等价变换1.1 原题到底在说什么按网上流传的常见版本这道题的输入输出约定大概是这样的输入 第一行一个整数 n表示数组长度1 ≤ n ≤ 1e5 第二行n 个整数 a[i]-1e9 ≤ a[i] ≤ 1e9 输出 一个整数表示把整个数组变成非递减序列的最小总代价“非递减”就是说最终数组 b 要满足b[1] ≤ b[2] ≤ b[3] ≤ ... ≤ b[n]每次把某个 a[i] 改成任意整数 x需要花费 |a[i] - x| 的代价。注意这里修改不限一次一个位置可以只改一次因为改到最终值就可以了改成中间值再改成最终值只会更贵所以每个位置只需要考虑它的最终值。数组整体可以负、可以正、可以重复代价可能很大答案需要用 64 位整数来存。1.2 “非递减”和“严格递增”的微妙差别很多第一次做的同学会把题目理解成“数组必须严格递增”也就是 b[i] b[i1]然后就开始纠结相等的情况怎么办。实际上题目明确要求的是非递减也就是允许 b[i] b[i1]这一点让问题的复杂度降低了不少。非递减和严格递增之间有个经典转化如果题目要求 b[i] b[i1]我们可以令 c[i] b[i] - i那么条件就变成 c[i] ≤ c[i1]也就是说非递增的“严格递增问题”可以等价转换成“非递减问题”。真遇到严格递增版本时只需要在输入上把 a[i] - i 再跑同样的算法即可。后面第 7 章会专门展开这个变式。1.3 先手动跑一个样例看一个简单例子a [3, 1, 4, 2]一种改法是变成 [1, 1, 2, 2]3 改成 1代价 21 保持不变代价 04 改成 2代价 22 保持不变代价 0总代价 4。另一种改法是变成 [3, 3, 4, 4]3 不变代价 01 改成 3代价 24 不变代价 02 改成 4代价 2总代价也是 4。两个最终数组完全不同但代价一样。这说明这道题不是简单地把高峰削平也不是简单地把低谷抬起来而是要找一组“全局平衡”的目标值。手动算这个例子能很快意识到局部贪心在这里不太可靠需要更结构化的思考方式。2. 贪心方案为什么全盘崩掉2.1 最直觉的“削峰”贪心很多人拿到题的第一反应是这样的从左往右扫只要发现 a[i] a[i-1]就把 a[i-1] 改小到 a[i]因为前面那个数太大了把“山峰”削掉后面的路就平了。我给这个策略起个名字叫“削峰贪心”。它的每一步都很容易实现而且在很多小样例上看起来是对的。比如 [3, 1, 4, 2]遇到 1 3把 3 改成 1代价 2遇到 2 4把 4 改成 2代价 2得到 [1,1,2,2]总代价 4看起来完美。于是很多人会顺势认为遇到逆序就削前面一定最优。但这种“局部看起来对”的直觉在稍微复杂一点的例子上立刻被击穿。2.2 反例完整演变[5,4,3,2,1]看一个完全“乱翘”的数组[5, 4, 3, 2, 1]用削峰贪心模拟一遍步骤当前数组动作本次代价累计代价第1步[5,4,3,2,1]5 → 411第2步[4,4,3,2,1]前面两个 4 → 31 1 23第3步[3,3,3,2,1]前面三个 3 → 21 1 1 36第4步[2,2,2,2,1]前面四个 2 → 11 1 1 1 410最终得到 [1,1,1,1,1]总代价 10。可是最优解其实是在“中间值”上取齐把 [5,4,3,2,1] 全部改成 [3,3,3,3,3]代价是|5-3| |4-3| |3-3| |2-3| |1-3| 2 1 0 1 2 6贪心花了 10最优只要 6。差距不是一点点。2.3 这个反例透露了什么本质削峰贪心的问题在于它每一步都在把前面的值往左拉拉完之后没有任何“反悔”的余地。等后面出现更小的数时它只能把前面已经改好的数再往小改改动的次数像雪球一样越滚越大。而真正的最优解往往在“削峰”和“抬谷”之间做折中。比如 [5,4,3,2,1] 的最优值 3不是左端点 1也不是右端点 5而是整个数组的中位数附近。这说明局部逆序的消除是一个全局决策峰值降到多少、低谷抬到多少和后续所有元素都有关。对称地如果你用“抬谷贪心”——遇到逆序就把后面的数抬高到前一个数——在 [1,2,3,4,5] 这种递增数组的反向版本上同样会崩浪费大量代价把整个数组抬到最大值。贪心的失败是必然的因为它丢掉了“对未来的选择权”。下面要讲的 DP 和反悔贪心本质上都是在保留这种选择权。3. DP建模把“最终值”纳入状态3.1 一个关键结论最终值只需要从原数组出现过的值里选在写 DP 之前先要确定枚举的对象。一个很容易想到的问题是最终值 b[i] 理论上可以是任意整数难道要枚举整个值域答案是不需要。存在一个最优解使得每个 b[i] 都取自原数组中出现过的值。我们可以把这组值排序去重后称为候选值。理由可以这样理解把最终值看成变量 x任何单点的修改代价 |a[i] - x| 是关于 x 的 V 形凸函数。多个这样的绝对值函数加在一起仍然是凸函数凸函数在两端约束下取极值时极值点一定落在某个绝对值函数的“断点”上也就是某个 a[i] 本身。更直白一点说如果某个最优解里出现了一个不在原数组中的值比如落在了两个相邻原值 v1 和 v2 中间那么把整个这一段一起向左平移到 v1或者向右平移到 v2总不会让代价变大而单调性也不会被破坏。这个结论意味着候选值数量 m 不会超过 n我们只需要对原数组排序去重即可完成离散化。3.2 状态与转移把非递减写进方程设离散化后的候选值数组为 vals[1..m]从小到大排列。定义dp[i][j] 处理完前 i 个数且第 i 个数最终值等于 vals[j] 的最小总代价转移方程是dp[i][j] |a[i] - vals[j]| min(dp[i-1][1], ..., dp[i-1][j])为什么取前缀最小值而不是全部最小值因为数组必须非递减前 i-1 个数的最后一个值不能超过第 i 个数的最终值 vals[j]所以只能在 dp[i-1][k] 中限制 k ≤ j。边界dp[1][j] |a[1] - vals[j]|最终答案ans min(dp[n][0], dp[n][1], ..., dp[n][m-1])这个 DP 的复杂度是 O(nm)如果再仔细处理可以用 O(nm) 的空间也可以用滚动数组压到 O(m)。3.3 一个能跑通的 O(n*m) 版本如果 n 比较小比如 n ≤ 5000下面的 C 写法完全够用#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorlong long a(n); for (int i 0; i n; i) cin a[i]; vectorlong long vals a; sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); int m vals.size(); const long long INF 4e18; vectorlong long dp(m), ndp(m); for (int j 0; j m; j) { dp[j] abs(a[0] - vals[j]); } for (int i 1; i n; i) { long long best INF; for (int j 0; j m; j) { best min(best, dp[j]); ndp[j] best abs(a[i] - vals[j]); } dp.swap(ndp); } cout *min_element(dp.begin(), dp.end()) \n; return 0; }注意这里best min(best, dp[j])是在枚举 j 的过程中同步维护min(dp[1..j])让复杂度从 O(nm^2) 降到 O(nm)。不过如果 n 和 m 都到 1e5O(n*m) 就是 1e10完全跑不动。hard 版题目的数据范围不会允许这个复杂度通过必须继续优化。4. 大根堆反悔贪心O(n log n) 的正解4.1 算法流程当数据范围到 1e5正确的做法是一个看起来非常“反直觉”的大根堆贪心。流程短到惊人ans 0 建一个大根堆 heap for x in a: heap.push(x) if heap.top() x: ans heap.top() - x heap.pop() heap.push(x) 输出 ans对核心就是这么几行。每读入一个数先把 x 压入大根堆。如果堆顶 top 大于当前 x说明前面某个“峰值候选值”比现在这个数还大出现了逆序风险。我们付出top - x的代价把这次逆序“抹平”。弹出 top再把 x 压入堆表示把候选目标值从 top 向左修正到 x同时保留一个未来的反悔机会。最终答案就是累加的 ans。这个算法的时间复杂度是 O(n log n)空间复杂度 O(n)完全能承受 1e5 的数据。4.2 为什么这个堆能代表 DP 的答案第一次看到这个做法的人都会怀疑这么简单的几行代码凭什么就是对最优解可以从 DP 的角度建立直觉。回看刚才的 DPdp[i][j] |a[i] - vals[j]| min(dp[i-1][1..j])每一步都在对上一层的 dp 数组做两件事先做前缀最小值压缩再加上一个 V 形绝对值函数。这两件事的组合会不断改变“当前最优目标值”的位置。其实整个算法等价于维护一条凸的代价曲线而大根堆里的元素正是这条凸曲线的斜率拐点。每次读入一个 x本质上是往这条曲线上叠加一个新的 V 形。如果这个 x 出现在当前最大拐点的左侧说明曲线的斜率翻转位置需要提前。原本拐点在 top现在要左移到 x代价就是 top - x弹掉旧的拐点压入新的 x就是把拐点集合更新掉。用更接地气的话讲堆里保存的是“若干个可反悔的候选值”。当新来的数太小之前的某个候选值就显得太高我们必须“花钱”把最高的候选值降下来并且把降下来的位置也留成一个新的候选值防止后面还有更小的数需要继续调整。这就是可反悔贪心的标准姿势。这个算法还有一个名字叫 slope trick在不少经典单调化题目里都能看到。面试或笔试遇到“修改代价为绝对值差 单调性限制”时可以优先想到这个套路。4.3 手算子样例堆的变化过程为了打消“是不是碰巧对”的疑虑我们来手动推两个样例。先看 [3, 1, 4, 2]读入 x压入后堆堆顶 toptop x ?累积 ans3[3]3否01[3, 1]3是3-1224[4, 1, 1]4否22[4, 2, 1, 1]4是4-224最终答案是 4和之前手动求出的最优解一致。再看魔鬼逆序 [5, 4, 3, 2, 1]读入 x调整细节累积 ans5堆 [5]top5不调整04top5 4ans 1pop 5 push 413top4 3ans 1pop 4 push 322top4堆里有另一个4ans 2pop 4 push 241top3ans 2pop 3 push 16最终 ans 6和 DP 最优解完全一致。顺带说一句堆里最终元素并不直接等于最优目标数组。它存的是候选拐点的集合最终数组可能需要额外构造但代价答案是准确的。5. Java、C、Python 三种实现的写法与性能坑5.1 C 的 priority_queue 提交模板C 里直接用priority_queueint默认就是大根堆非常省事。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; priority_queueint pq; long long ans 0; for (int i 0; i n; i) { int x; cin x; pq.push(x); if (pq.top() x) { long long top pq.top(); ans top - x; pq.pop(); pq.push(x); } } cout ans \n; return 0; }容易踩的坑有两个ans 必须用 long long因为最坏情况代价可以是 n 乘以值域跨度到 1e14 级别。判断条件里不能先 pop 再判断。正确顺序是先 push再看堆顶有必要才 pop。如果写反会漏掉当前 x 作为候选值的资格。5.2 Java 的 PriorityQueue 细节Java 的PriorityQueue默认是小根堆需要传一个反转比较器import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); int n Integer.parseInt(st.nextToken()); PriorityQueueInteger pq new PriorityQueue(Collections.reverseOrder()); long ans 0; st new StringTokenizer(br.readLine()); for (int i 0; i n; i) { if (!st.hasMoreTokens()) { st new StringTokenizer(br.readLine()); } int x Integer.parseInt(st.nextToken()); pq.offer(x); if (pq.peek() x) { ans (long) pq.poll() - x; pq.offer(x); } } System.out.println(ans); } }这里有个容易被忽略的点堆里存的是Integer元素本身在 int 范围内没问题但累加 ans 时一定要先转 long。如果写成ans pq.poll() - x在 Java 里Integer会先自动拆箱成 int 再相加两个极端值相减可能在 int 范围内不溢出但累加后会溢出所以写成(long) pq.poll() - x更稳妥。输入上如果第二行数字保证在同一行简单的readLine拆分就够。如果担心数据分散在多个换行里就每次用hasMoreTokens()检查一下必要时再readLine()补一行。5.3 Python 的 heapq 模拟大根堆Python 的heapq只有小根堆模拟大根堆的标准做法是存负数。import sys import heapq def solve(): data list(map(int, sys.stdin.buffer.read().split())) if not data: return n data[0] arr data[1:1 n] heap [] ans 0 for x in arr: heapq.heappush(heap, -x) top -heap[0] if top x: ans top - x heapq.heappop(heap) heapq.heappush(heap, -x) print(ans) if __name__ __main__: solve()注意两个细节压入堆的是-x所以读取堆顶时要取反top -heap[0]。逆序发生时先heappop再heappush(-x)这个顺序不要反。Python 的整数没有溢出问题所以 ans 随意加。5.4 复杂度与注意事项小结语言数据结构时间复杂度空间复杂度主要注意点Cpriority_queueO(n log n)O(n)ans 用 long long先 push 再判断JavaPriorityQueueO(n log n)O(n)reverseOrderans 累加前转 longPythonheapq 存负数O(n log n)O(n)堆顶取反heappop 后 push 负 x三种实现的算法逻辑完全一致复杂度也几乎没有差别笔试时选自己最熟的语言写就好。6. 对拍验证从“感觉对”到“确定对”6.1 小数据暴力对拍器如果只是背下代码心里始终会不踏实。我的习惯是写一个暴力枚举版程序再写一个正解版用随机小数据对拍。暴力版可以用 Python 写思路很简单候选值取原数组去重排序后的集合用笛卡尔积枚举所有可能的最终数组检查是否非递减记录最小代价。from itertools import product def brute(a): vals sorted(set(a)) n len(a) best 10**18 for b in product(vals, repeatn): if all(b[i] b[i 1] for i in range(n - 1)): cost sum(abs(a[i] - b[i]) for i in range(n)) best min(best, cost) return best当 n ≤ 7、候选值个数 ≤ 7 时最多 7^7 823543 种组合足够在几秒内跑完。然后写一个随机数据生成器不断生成小数组同时调用暴力和正解比较输出import random import subprocess import sys def generate_case(n): return [random.randint(-3, 3) for _ in range(n)] # 假设你已经把正解编译成 solve.out for t in range(1000): n random.randint(1, 6) a generate_case(n) input_data f{n}\n{ .join(map(str, a))}\n with open(input.txt, w) as f: f.write(input_data) brute_ans brute(a) # 运行两个可执行文件并比较 p1 subprocess.run([./solve_ac], stdinopen(input.txt), capture_outputTrue, textTrue) p2 subprocess.run([./solve_brute], stdinopen(input.txt), capture_outputTrue, textTrue) if p1.stdout.strip() ! p2.stdout.strip() or p1.stdout.strip() ! str(brute_ans): print(Mismatch!, a) sys.exit(1) print(all ok)对拍能找到手工构造不出来的隐蔽边界错误是检验贪心/DP 题的利器。6.2 边界用例与随机数据手动测试的几个关键用例n 1数组只有一个数例如 [7]不需要修改输出 0。数组已经非递减例如 [1, 2, 3, 4]输出 0。数组全部相等例如 [2, 2, 2]输出 0。严格递减数组例如 [5, 4, 3, 2, 1]输出 6。负数和正数混合例如 [-5, 3, -2]需要程序正确处理。重复候选值很多例如 [2, 2, 2, 1, 1, 1]容易暴露堆里重复元素的处理问题。随机数据方面可以生成n 在 1 到 8 之间的小数据a[i] 在 -5 到 5 之间的中等数据a[i] 在 -1e9 到 1e9 的大数据用于检查溢出和性能。6.3 笔试现场的几个检查点如果是在笔试场景下写这道题我会额外检查这几件事读入时确认 n 和 a[i] 的类型不要因为数组元素超出 int 而改用 long 读入其实元素在 int 范围内但代价要用 long。堆操作的顺序先 push再比较再 pop最后再 push。顺序错了答案就会飘。Java 和 C 的 ans 累加都要用 64 位整数。Python 注意把-xpush 进去之后比较用的是-heap[0]不是heap[0]。如果题目要求多组测试数据记得每组之间清空堆并把 ans 归零。这些点看着细小但笔试时最容易犯错。7. 变式扩展与这类题的通用思考7.1 严格递增怎么改如果题目改成“最终数组必须严格递增”只需要做一步变换把 a[i] 替换成 a[i] - i然后对替换后的数组跑非递减算法即可。原因是b[i] b[i1] 等价于 b[i] - i ≤ b[i1] - (i1)。所以严格递增数组经过减去下标后会变成非递减数组。修改代价不变因为变换只是平移。举个例子a [3, 1, 2] 要求严格递增那么先变成 c [3, 1-1, 2-2] [3, 0, 0]接着求解 c 的非递减问题。这个技巧在很多单调性题目里都通用。7.2 修改成单调不增的对称解法如果题目要求的是“非递增”即 b[i] b[i1]可以用对称处理第一种方法把整个数组反转然后跑非递减算法第二种方法把所有元素取负然后跑非递减算法最后答案不变。因为非递增数组乘上 -1 之后就是非递减数组修改代价是 |a[i] - b[i]|对负号完全免疫。7.3 绝对值代价类题目的共性套路这一类题见得多了之后会发现一个明显的规律只要看到“修改代价为绝对值差”加上“单调性限制”大概率不是单纯排序题也不是简单贪心题。可以考虑的方向有三个。如果数据范围小直接离散化 DP状态里带上当前位置最终值。如果数据范围大优先怀疑是凸优化问题思考用大根堆维护斜率拐点也就是 slope trick。如果允许把整个序列改成同一个值最小代价就是原序列的中位数这个结论可以用来验证一些小样例。绝对值函数天然是凸的加在一起还是凸的所以很多这类题最后都会落在“找拐点”上。理解了这一点以后再看到类似题目就不会觉得堆算法是凭空蹦出来的了。我自己的体会是这题的难点不在代码而在“愿不愿意放弃局部贪心去相信一个可以反悔的候选值集合”。我第一次写的时候用削峰贪心交上去WA 得莫名其妙后来把 [5,4,3,2,1] 手工跑了一遍才发现问题不是少考虑了一个分支而是整个决策结构就不对。强烈建议读者把三种语言的代码都手敲一遍再用暴力对拍跑上几百组随机数据这样才能真正掌握这类“绝对值代价 单调化”的题目套路。