蚂蚁春招 3 月 12 日这场笔试第一题 100 分题目名叫“增加or减少”。刷过笔试题的朋友应该秒懂——凡是“增加或减少”这四个字多半就是给你一个数组让你一次把某个元素 1 或者 -1然后问最少操作步数满足某种条件。这类题在互联网公司的在线测试里出现频率极高考的不是你会不会背模板而是三样基本功建模能力能不能把题目转成数学表达式、排序与中位数的敏感度、以及三种主流语言的落笔速度。这道题适合三类人阅读准备暑期实习和秋招笔试的应届生想在 Java / C / Python 三门语言之间切换练手感的同学以及想借一道“简单但不白给”的题目复习中位数性质和整数溢出的老手。下面我把题目还原、思路证明、三种语言实现、在线测试方法、以及我实际踩过的坑一次讲完。1. 题目还原与考点拆解1.1 我拿到的题目长什么样网上回忆版的大意是给定一个长度为 n 的整数数组 a。每次操作可以选中任意一个元素将它增加 1 或减少 1。请问最少需要多少次操作才能使数组中所有元素的值相等输出最小操作次数。约束一般给到 n ≤ 10^5a[i] ≤ 10^9。别小看这个范围它决定了两个坑一是算法必须做到 O(n log n) 或 O(n)二是答案会超过 int 的取值范围。举个具体例子输入数组一种最优方案最小操作次数[1, 2, 3]三个数都变成 2113-12[5, 5, 5]不需要操作0[1, 2, 100]三个数都变成 298 步来自 100→299注意第三组如果目标选 34平均值需要 33 32 66 131 步远大于 99。这里已经能闻出味道了最优目标和中位数有关和平均数无关。1.2 它到底在考什么从考官视角看这个题想验证四件事。第一能不能把一个“操作类”问题翻译成数学表达式。假设所有元素最终变成 X那么操作总数就是 C(X) Σ|a[i] - X|问题变成找整数 X 让 C(X) 最小。这一步没想通后面全是白搭。第二知不知道一维绝对值求和的最小值点在中位数。这是 LeetCode 462 的核心也是“货仓选址”这类经典贪心题的根。很多人会下意识选平均数这就是考点。第三会不会处理大整数。n 取 10^5a[i] 取 10^9最坏情况下操作数接近 10^14Java 的 int、C 的 int 都会溢出一塌糊涂。基础不牢的同学在这一题上翻车是最可惜的。第四边界情况是不是严谨。n1 时答案是 0数组全相等时也是 0偶数长度时中间区间内任意整数都可以当目标。这些在笔试的自测环节都要点一遍。1.3 为什么这道题值得写我在准备春招时把蚂蚁近两年笔试题捋过一遍第一题大多落在“排序 贪心”“双指针”“前缀和”这个难度档。这道“增加or减少”正好是其中的代表它不像动态规划那样需要大量训练积累但对思路的干净程度和语言的熟练度要求很高。换句话说它是一道“会者三分钟不会者三小时”的题。把这道题吃透等于把“中位数求最小绝对距离”这一整套模板复制进脑子后面再看货仓选址、看同源变形题会顺畅很多。2. 思路推导从直觉到严格证明2.1 先别急着写代码把式子列出来拿到题目我建议先在草稿纸上写假设最终共同值是 X总操作数 |a[0] - X| |a[1] - X| ... |a[n-1] - X|。这一步看起来废话其实是整个问题的定盘星。接着考虑 X 每向右移动 1C(X) 会发生什么变化。每个在 X 左侧的元素值小于等于 X因为基准变大了距离都会增加 1每个在 X 右侧的元素距离都会减少 1。所以 C(X) 的变化量约等于“左边元素个数 - 右边元素个数”。当这个变化量为负时向右走能让总代价变小当它为正时向左走更划算两边个数相等时代价达到谷底——这个位置就是中位数。这段推导对做过的同学来说是常识对没做过的同学来说它把“为什么用中位数”从经验记忆升级成了可推导的结论面试时讲给面试官听是非常加分的。2.2 中位数最优的严格证明还有更漂亮的证明方式把排序后的数组两两配对b[0] 配 b[n-1]b[1] 配 b[n-2]依此类推。对任意一对 (p, q)假设 p ≤ q有|p - X| |q - X| q - p当 X 落在 [p, q] 区间内 |p - X| |q - X| q - p当 X 落在 [p, q] 区间外。也就是说只要 X 能同时落在每一对的区间里总代价就能取到理论下界 Σ(q - p)。这些区间的交集是什么正是数组的中位数偶数长度时是两个中间值之间的整个闭区间。下界可达所以中位数就是最优目标最小代价等于 Σ|b[i] - 中位数|。这个证明还有一个副产品偶数长度时目标 X 不唯一中间两个值之间的任何整数都可以。所以笔试里要是只要求输出最小操作数你取排序后 a[n/2]“上中位”完全没问题。2.3 三个常见误区误区一用平均数。平均数最小化的是平方距离不是绝对距离。拿 [1, 2, 100] 一试便知平均值 34 要花 131 步中位数 2 只要 99 步。误区二暴力枚举所有可能 X。X 的范围有 10^9 那么大直接枚举肯定超时。但注意最小值点只可能出现在数组取值附近所以理论上只用检查排序后数组的中间几个值即可。误区三认为一定要改变数组。如果数组全相等答案就是 0不需要真的“操作”任何元素。写代码时直接走中位数公式也能得到 0但理解上别忽略这种平凡情况。3. 三种语言的实现与食用指南3.1 Java 版本与逐行解读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)); int n Integer.parseInt(br.readLine()); StringTokenizer st new StringTokenizer(br.readLine()); long[] a new long[n]; for (int i 0; i n; i) { a[i] Long.parseLong(st.nextToken()); } Arrays.sort(a); long mid a[n / 2]; long ans 0; for (long x : a) { ans Math.abs(x - mid); } System.out.println(ans); } }几个要点。第一数组声明成 long[]读入用 Long.parseLong这是防止溢出的第一道闸门。第二n 为偶数时 a[n/2] 取到的是上中位前面证明过它一样是合法最优解。第三笔试环境里 BufferedReader 比 Scanner 快不少数据量到 10^5 时感知不明显但养成习惯没坏处。如果输入格式不保证一行读完可以改成循环读或者干脆用 Scanner 图省事这题数据量用 Scanner 也能过。3.2 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]; } sort(a.begin(), a.end()); long long mid a[n / 2]; long long ans 0; for (long long x : a) { ans llabs(x - mid); } cout ans \n; return 0; }这里最容易翻车的是 abs 函数。虽然 C11 之后 std::abs 有 long long 重载但在旧编译环境下容易出现类型截断而且using namespace std混用abs时也容易让人忽略类型问题。稳妥做法是用llabs或者手写long long diff x mid ? x - mid : mid - x;。另外别忘了ios::sync_with_stdio(false)和cin.tie(nullptr)笔试输入量大时这两行能省下不少时间。最后注意下标排序后取第 n/2 个元素下标从 0 开始别习惯性写成 n/2 1。3.3 Python 版本与写码思路import sys def main(): data list(map(int, sys.stdin.read().split())) n data[0] a data[1:1 n] a.sort() mid a[n // 2] ans sum(abs(x - mid) for x in a) print(ans) if __name__ __main__: main()Python 写法最简洁但有两个细节值得注意。一是读入用sys.stdin.read().split()而不是input()单行读因为题目可能把 n 和数组拆成多行或者行内有多余空格一次性读入再切片最稳。二是 Python 的 int 是任意精度不用担心溢出但如果你在 Java 和 Python 之间切换做题脑子里始终要有一个“要不要用 long”的开关别把 Python 的习惯带回 Java。3.4 三版实现复杂度对比语言时间复杂度空间复杂度核心注意点JavaO(n log n)O(n)long[]Math.abs(long)CO(n log n)O(n)llabs记得关同步PythonO(n log n)O(n)read().split() 读入三者核心思路完全一致排序 → 取中位 → 累加绝对差。区别只在语法细节和溢出处理上。笔试前把这三版各写一遍能帮你快速暴露自己不熟悉的语言细节。4. 在线测试与自测方法4.1 这道题能在哪里验证这道题的原型就是 LeetCode 462「Minimum Moves to Equal Array Elements II」题面和“增加or减少”几乎一一对应你可以直接去上面提交验证。提交时注意LeetCode 的函数签名接收的是 int[] 数组它自带的用例相对温和但按笔试的真实约束答案可能超过 int 范围所以本地验证时一定要按 long 算再自己加压大数用例。如果你不想依赖外部平台本地搭一个简单的测试脚本是最踏实的做法。把上面任意一版解法封装成函数再配合一个读文件的小壳子就能当评测机用。提示笔试时如果忘了公式最稳的兜底办法是先写暴力枚举小数据验证思路再优化成排序取中位数。很多同学上来就写正解结果边界写错反而不如“暴力 优化”两步走来得稳。4.2 手写暴力对拍模板这里给一个我常用的“暴力对拍”策略。暴力版的思路是最终值一定在 min(a) 到 max(a) 之间枚举这个区间内的每个整数当目标算一遍代价取最小。虽然复杂度高但结果一定对专门用来验证优化版。import random def fast(a): a sorted(a) mid a[len(a) // 2] return sum(abs(x - mid) for x in a) def brute(a): best float(inf) for target in range(min(a), max(a) 1): best min(best, sum(abs(x - target) for x in a)) return best for _ in range(10000): n random.randint(1, 8) a [random.randint(-5, 5) for _ in range(n)] if fast(a[:]) ! brute(a[:]): print(mismatch, a, fast(a), brute(a)) break else: print(all ok)跑一万组随机小数据如果 fast 和 brute 全都一致基本可以放心提交。这套对拍模板可以迁移到任何“暴力可解”的笔试题上养成习惯后笔试里的低级失误会少很多。4.3 边界用例清单提交前我建议按下表自测用例期望结果说明n1a[7]0单元素无需操作[10, 1]9偶数长度目标可取 [1,10] 内任意整数[1, 1, 1]0全相等[1000000000, 1, 1, 1, ..., 1]接近 10^14验证 long别溢出[5, 4, 3, 2, 1]6逆序数组中位数 3最后一行算一下都变成 3代价是 |5-3| |4-3| 0 |2-3| |1-3| 2 1 0 1 2 6。这类手算用例能帮你快速定位排序、下标、abs 哪一步写错。5. 易错点排查与同源变形5.1 高频翻车现场我整理了一份问题速查表都是真实笔试里常见的情况。现象原因解决办法结果比正确答案大很多用了平均数当目标换成中位数小数据对大数据错int 溢出全链路用 long/long long输出负数或乱码C abs 对 long long 截断用 llabs 或手写三目数组没排序就取中位忘了排序sort 之后再取 a[n/2]读入只读了半行输入有多行用 read().split() 一次性读除了一张表我还想多说一句笔试里“卡住五分钟”和“完全不会”是两码事。遇到这种题先把式子列出来把暴力写出来再谈优化。过程分和正确分同样重要。5.2 同源变形让数组变成非递减如果题目不是“全部相等”而是“一次操作可以增加或减少任意元素 1使最终数组非递减求最小操作数”思路就换成了贪心 大顶堆。核心代码如下priority_queuelong long pq; long long ans 0; for (int i 0; i n; i) { pq.push(a[i]); if (pq.top() a[i]) { ans pq.top() - a[i]; pq.pop(); pq.push(a[i]); } }这个解法的直观理解是每次遇到“前面有个数比当前数大”的情况就把这对矛盾在最优位置“削平”堆里维护的是当前的候选高度。想彻底搞懂可以去看经典题 “Sonya and Problem Wihtout a Legend” 的题解。我只提醒一句——这类变形题在笔试里也出现过看到“增加或减少”先别急着套中位数先确认题目要求的是“全部相等”还是“单调不降”。5.3 还能怎么扩展如果笔试时间充足你可以再想想两个方向。方向一把 O(n log n) 优化到 O(n)。排序的本质只是为了找中位数如果你会用快速选择nth_element / 维护一半元素的堆可以把复杂度压到 O(n)。对 10^5 的数据这不是必须的但面试聊复杂度时可以提。方向二改成二维。如果数组变成二维平面上的点每次操作让某个点的 x 或 y 增加或减少 1要让所有点重合答案就是 x 方向的绝对值距离和加上 y 方向的两个维度互相独立。这是曼哈顿距离的经典结论和今天这道题一脉相承。我实际刷这道题时的体会是Java、C、Python 三版代码加起来不到 60 行但真正值钱的不是代码是“先列式子、再证中位数、最后处理溢出”这条解题链。笔试现场如果能把这几步走稳第一题 100 分基本不会丢。最后再分享一个小技巧平时刷题我习惯把同源题归一个文件夹LeetCode 462、货仓选址、二维曼哈顿中位数放一起考前十分钟翻一遍比临时抱佛脚背模板有效得多。祝大家春招顺利第一题一把过。