企业官网建设流程全解析

蚂蚁春招 3 月 12 日这场笔试，第一题 100 分，题目名叫“增加or减少”。刷过笔试题的朋友应该秒懂——凡是“增加或减少”这四个字，多半就是给你一个数组，让你一次把某个元素 +1 或者 -1，然后问最少操作步数满足某种条件。这类题在互联网公司的在线测试里出现频率极高，考的不是你会不会背模板，而是三样基本功：建模能力（能不能把题目转成数学表达式）、排序与中位数的敏感度、以及三种主流语言的落笔速度。

这道题适合三类人阅读：准备暑期实习和秋招笔试的应届生，想在 Java / C++ / Python 三门语言之间切换练手感的同学，以及想借一道“简单但不白给”的题目复习中位数性质和整数溢出的老手。下面我把题目还原、思路证明、三种语言实现、在线测试方法、以及我实际踩过的坑一次讲完。

1. 题目还原与考点拆解

1.1 我拿到的题目长什么样

网上回忆版的大意是：

给定一个长度为 n 的整数数组 a。每次操作可以选中任意一个元素，将它增加 1 或减少 1。请问最少需要多少次操作，才能使数组中所有元素的值相等？输出最小操作次数。

约束一般给到 n ≤ 10^5，a[i] ≤ 10^9。别小看这个范围，它决定了两个坑：一是算法必须做到 O(n log n) 或 O(n)，二是答案会超过 int 的取值范围。

举个具体例子：

注意第三组，如果目标选 34（平均值），需要 33 + 32 + 66 = 131 步，远大于 99。这里已经能闻出味道了：最优目标和中位数有关，和平均数无关。

1.2 它到底在考什么

从考官视角看，这个题想验证四件事。

第一，能不能把一个“操作类”问题翻译成数学表达式。假设所有元素最终变成 X，那么操作总数就是 C(X) = Σ|a[i] - X|，问题变成：找整数 X 让 C(X) 最小。这一步没想通，后面全是白搭。

第二，知不知道一维绝对值求和的最小值点在中位数。这是 LeetCode 462 的核心，也是“货仓选址”这类经典贪心题的根。很多人会下意识选平均数，这就是考点。

第三，会不会处理大整数。n 取 10^5，a[i] 取 10^9，最坏情况下操作数接近 10^14，Java 的 int、C++ 的 int 都会溢出一塌糊涂。基础不牢的同学在这一题上翻车是最可惜的。

第四，边界情况是不是严谨。n=1 时答案是 0，数组全相等时也是 0，偶数长度时中间区间内任意整数都可以当目标。这些在笔试的自测环节都要点一遍。

1.3 为什么这道题值得写

我在准备春招时把蚂蚁近两年笔试题捋过一遍，第一题大多落在“排序 + 贪心”“双指针”“前缀和”这个难度档。这道“增加or减少”正好是其中的代表：它不像动态规划那样需要大量训练积累，但对思路的干净程度和语言的熟练度要求很高。换句话说，它是一道“会者三分钟，不会者三小时”的题。把这道题吃透，等于把“中位数求最小绝对距离”这一整套模板复制进脑子，后面再看货仓选址、看同源变形题会顺畅很多。

2. 思路推导：从直觉到严格证明

2.1 先别急着写代码，把式子列出来

拿到题目，我建议先在草稿纸上写：假设最终共同值是 X，总操作数 = |a[0] - X| + |a[1] - X| + ... + |a[n-1] - X|。这一步看起来废话，其实是整个问题的定盘星。

接着考虑 X 每向右移动 1，C(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; vector<long 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 函数。虽然 C++11 之后 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 三版实现复杂度对比

三者核心思路完全一致：排序 → 取中位 → 累加绝对差。区别只在语法细节和溢出处理上。笔试前把这三版各写一遍，能帮你快速暴露自己不熟悉的语言细节。

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 边界用例清单

提交前我建议按下表自测：

最后一行算一下：都变成 3，代价是 |5-3| + |4-3| + 0 + |2-3| + |1-3| = 2 + 1 + 0 + 1 + 2 = 6。这类手算用例能帮你快速定位排序、下标、abs 哪一步写错。

5. 易错点排查与同源变形

5.1 高频翻车现场

我整理了一份问题速查表，都是真实笔试里常见的情况。

除了一张表，我还想多说一句：笔试里“卡住五分钟”和“完全不会”是两码事。遇到这种题，先把式子列出来，把暴力写出来，再谈优化。过程分和正确分同样重要。

5.2 同源变形：让数组变成非递减

如果题目不是“全部相等”，而是“一次操作可以增加或减少任意元素 1，使最终数组非递减，求最小操作数”，思路就换成了贪心 + 大顶堆。核心代码如下：

priority_queue<long 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、货仓选址、二维曼哈顿中位数放一起，考前十分钟翻一遍，比临时抱佛脚背模板有效得多。祝大家春招顺利，第一题一把过。