上周有个备考华为OD机考的朋友给我发了一道题说C卷里碰到“最佳对手”题目名听着像是博弈论读完题干又觉得像匹配问题脑子里瞬间冒出匈牙利算法、状压DP这些词结果一看数据范围N最大能到10万当场心态就崩了。我让他把原题截图发过来仔细读完发现这题的题眼根本不在“对手”两个字上而在“两两分组”和“实力差总和最小”这两个条件上。解法朴素到你可能不信排序然后相邻配对五分钟就能AC。但想明白为什么能这么做以及不同语言在机考环境里怎么写不容易翻车才是这篇文章真正想聊的东西。下面所有内容都围绕华为OD机考C卷里流传最广的“最佳对手 / 实力差距最小总和”这个版本展开我会给出Java、Python、JavaScript、C/C、Go五种语言的完整可运行代码再把机考里最容易丢分的输入输出、整数溢出、边界条件这些细节全部摊开讲。不管你刚开始刷OD题库还是已经刷了一两百道在冲刺阶段这篇都能帮你省下不少踩坑的时间。1. 先把题面掰开这题到底要你算什么1.1 题目原型与样例不同题库对这道题的翻译略有差异但逻辑等价。我按最常见的版本描述一下一共有N个玩家每个玩家有一个实力值。现在需要把玩家两两分组每组两人进行对战。为了保证公平要求每一组两个玩家的实力差不能超过K。请问能否把全部N个玩家都完成分组如果能输出所有分组实力差总和的最小值如果不能输出-1。输入格式是这样的第一行两个整数 N K 第二行N个整数代表每个玩家的实力值输出要求如果能全部分组输出最小实力差总和否则输出-1。看一眼样例会更直观。假设输入是4 3 1 3 2 4排序后数组变成[1, 2, 3, 4]两两相邻配对是(1,2)和(3,4)差值分别是1和1总和2所以输出2。如果换成(1,3)和(2,4)差值总和是4比2大(1,4)和(2,3)也是4。可见相邻配对确实是最优。再看一个无解的例子4 0 10 20 30 40K等于0表示每组两个人的实力值必须完全相同显然这四个数没有相等的所以输出-1。1.2 题面文字背后的三个隐藏条件我见过很多人栽在这道题上不是因为不会排序而是没读懂题面里的隐藏条件。第一N为偶数。这个条件直接告诉你所有人必须被分完不存在有人轮空的情况。有些变体题目里N可以是奇数那种情况就要用另一套动态规划后文我会单独开一节讲。第二“把全部N个玩家都完成分组”这句话决定了这是全配对问题。如果题目换成“从中选出尽可能多的两人组”解法立刻从贪心变成DP。这也是我在评论区看到大家吵架的根源——有人贴的代码是动态规划有人贴的是贪心其实都没错但题目版本可能根本不是同一个。第三“实力差不能超过K”中的K不是让你去求的东西而是一个合法性过滤器。你只需要在配对时判断差值是否超过K不需要在K上做二分答案也不需要把K当成背包容量。1.3 为什么网上有人用DP有人用贪心全网搜“最佳对手”会出现两种说法一种要求全配对另一种要求“配对数量优先差值总和最小”。这两种题的数据范围也可能不一样全配对版本通常保证N是偶数且必须完整匹配后者N可能是奇数允许有人落单。所以我建议刷题的时候点开题解之前先确认题目版本否则抄代码都是白抄。1.4 双机位考试环境下的实际感受华为OD机考的双机位监控下你面前一个摄像头侧后方还有一个操作都被记录。这种环境里你基本不可能依赖本地IDE的代码补全平时写代码用惯了Arrays.sort或者a.sort()自动补全真到考试编辑器里手写的时候很容易卡壳。所以平时练习建议直接用在线编辑器或者最朴素的文本编辑器敲完整代码尤其是主类名、包名、输入输出模板要形成肌肉记忆。2. 核心思路排序相邻配对为什么就是最优解2.1 一个直觉实验把实力值画在数轴上比如 1、2、100、101 这四个点。要让两条线段的总长度最小直觉上就是让相邻的两个点连在一起1-2 连一条100-101 连一条总长度2。如果硬要交叉配对1-100、2-101总长度是1981-101、2-100 也是198。为什么交叉会这么亏因为排序之后所有点从左到右排列一条跨越很多点的长边必然会把无数个点甩在一边而另一边又有一条同样长的长边两段长边叠加自然就远远大于把中间那些点各自相邻连接的距离了。这背后的数学结论是对于数轴上一组已经排序的点在所有两两匹配方案中相邻匹配的总距离最小。任何交叉匹配都可以通过交换端点变成非交叉匹配同时总距离不会增加。反复进行这种消除交叉的交换最终就一定得到相邻配对的形态。2.2 严谨一点的证明应对面试追问如果你担心机考之后的性格面或技术面被追问可以把这个证明逻辑记一下。假设存在两个配对 ((a_i, a_j)) 和 ((a_p, a_q))索引满足 (i p j q)这就是一组交叉匹配。由于数组已经排序所以有 (a_i \le a_p \le a_j \le a_q)。拆开这两对的距离和[ |a_i-a_j| |a_p-a_q| a_j - a_i a_q - a_p ]如果把它调整成 ((a_i, a_p)) 和 ((a_j, a_q)) 这两对相邻匹配距离和是[ |a_i-a_p| |a_j-a_q| a_p - a_i a_q - a_j ]两者做差[ (a_j - a_i a_q - a_p) - (a_p - a_i a_q - a_j) 2(a_j - a_p) \ge 0 ]也就是说交叉匹配的距离和一定不小于改成相邻匹配后的距离和。所以最优解一定可以写成相邻配对的形式。2.3 加上K限制之后相邻配对仍然成立吗这可能是全题最容易被追问的细节如果相邻配对里有一对差值刚好超过K是不是代表一定无解答案是肯定的。我们可以先看一个更直观的版本如果排序后第一对(a[1], a[2])的差都大于K那么a[1]和a[3]、a[4]……任何人的差值只会更大都不满足K的限制所以a[1]根本找不到配对伙伴全局无解。再看中间位置的情况。假设合法方案中存在交叉配对(x1, x3)和(x2, x4)即[ x_3 - x_1 \le K, \quad x_4 - x_2 \le K ]因为 (x_2 \le x_3)所以 (x_2 - x_1 \le x_3 - x_1 \le K)第一对相邻配对(x1, x2)必然合法。又因为 (x_3 \le x_4)所以 (x_4 - x_3 \le x_4 - x_2 \le K)第二对相邻配对(x3, x4)也必然合法。这说明交叉合法对可以被替换成相邻合法对替换之后仍然合法而且距离和不会变大。不断消除交叉最终得到的就是排序后从前往后按顺序两两配对。所以结论很干净判断是否有解只需要看排序后相邻配对中是否出现差值大于K的对求最小总和也只需要把相邻配对的距离和累加出来。2.4 复杂度与数据范围整体复杂度是排序O(N log N)加上线性扫描O(N)。N到10万毫无压力就算N到100万也能轻松扛住。内存上只需要一个长度为N的数组O(N)。真正需要警惕的是数据类型。如果实力值上限到10的9次方K也到10的9次方那么N/2对差值的总和可能达到5乘以10的13次方远超32位整数范围。所以Java里要用longC用long longGo用int64Python因为自带大整数所以不用操心。3. 五种语言实现直接可跑的AC模板这一节给出五种语言的完整代码。注意华为OD机考通常要求提交一个完整可运行的程序不是只写一个函数所以每个代码都包含完整的输入输出处理。3.1 Java版本Java在机考里非常常见但有两个点容易踩主类名必须叫Main不能带package数据量大时用Scanner没问题但如果追求速度可以换BufferedReader。因为这里是按空白符读取Scanner的nextInt、nextLong都不会受换行影响代码可读性也更好。import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); long k sc.nextLong(); long[] a new long[n]; for (int i 0; i n; i) { a[i] sc.nextLong(); } Arrays.sort(a); long ans 0; for (int i 0; i n; i 2) { long diff a[i 1] - a[i]; if (diff k) { System.out.println(-1); return; } ans diff; } System.out.println(ans); } }两个细节说明一下。第一实力值用long数组而不是int防止总和溢出。第二一旦发现相邻差值大于K直接输出-1并结束程序不需要继续扫描。3.2 Python版本Python写起来最简洁但机考环境里Python有个经典坑输入的第二行可能因为换行被拆成多行如果你只写一行a list(map(int, input().split()))遇到数据跨行就会少读。稳妥做法是循环读取直到数组长度达到N。import sys def solve(): input sys.stdin.readline n, k map(int, input().split()) a [] while len(a) n: a.extend(map(int, input().split())) a.sort() ans 0 for i in range(0, n, 2): diff a[i 1] - a[i] if diff k: print(-1) return ans diff print(ans) if __name__ __main__: solve()Python本身是动态类型不需要考虑溢出问题。但要注意while len(a) n这个循环如果输入文件末尾有额外空行input().split()返回空列表extend空列表不会报错循环继续直到遇到真正包含数字的行。这个写法在牛客、华为OD的在线编辑器里都很稳。3.3 JavaScript版本JavaScript在OD机考中也开放但用的是Node.js环境。最容易被坑的是sort()JS默认按字符串排序直接对数字数组调用a.sort()会得到[1, 10, 2, 20]这种结果。必须传比较函数(x, y) x - y。const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout }); const lines []; rl.on(line, (line) { lines.push(line.trim()); }); rl.on(close, () { const first lines[0].split( ).map(Number); const n first[0]; const k first[1]; const a []; for (let i 1; i lines.length; i) { if (lines[i] ) continue; a.push(...lines[i].split( ).map(Number)); } a.sort((x, y) x - y); let ans 0; for (let i 0; i n; i 2) { const diff a[i 1] - a[i]; if (diff k) { console.log(-1); return; } ans diff; } console.log(ans); });这里多写了一个循环把所有输入行都拼到a数组里就是为了防止第二行数据过长被系统换行。Node.js的readline按行触发拼完之后再统一处理逻辑最稳妥。3.4 C/C版本C在机考里最大的优势是cin天然按空白符读取不怕换行。不过要记得关同步流否则数据量大时速度会吃亏。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; long long k; cin n k; vectorlong long a(n); for (int i 0; i n; i) { cin a[i]; } sort(a.begin(), a.end()); long long ans 0; for (int i 0; i n; i 2) { long long diff a[i 1] - a[i]; if (diff k) { cout -1 \n; return 0; } ans diff; } cout ans \n; return 0; }如果你平时用C语言直接裸写qsort会稍微麻烦一点。机考建议直接用C的STLsort比手写快排稳定也不容易出错。3.5 Go版本Go的输入处理比前几种语言都要啰嗦一点但逻辑并不复杂。核心是bufio.Scanner配合strings.Fields按空白符读取所有数字。package main import ( bufio fmt os sort strconv strings ) func main() { scanner : bufio.NewScanner(os.Stdin) scanner.Buffer(make([]byte, 1024*1024), 1024*1024) scanner.Scan() firstLine : strings.Fields(scanner.Text()) n, _ : strconv.Atoi(firstLine[0]) k, _ : strconv.ParseInt(firstLine[1], 10, 64) a : make([]int64, 0, n) for scanner.Scan() { fields : strings.Fields(scanner.Text()) for _, s : range fields { v, _ : strconv.ParseInt(s, 10, 64) a append(a, v) } } sort.Slice(a, func(i, j int) bool { return a[i] a[j] }) var ans int64 0 for i : 0; i n; i 2 { diff : a[i1] - a[i] if diff k { fmt.Println(-1) return } ans diff } fmt.Println(ans) }这里有个细节bufio.Scanner默认缓冲区大小只有64KB如果N到10万第二行数字长度可能超过这个值所以用scanner.Buffer把缓冲区调大。这个坑在牛客平台上很容易踩但在本地测试时因为数据量小往往发现不了。4. 机考实操最容易丢分的三个细节代码本身不复杂但我看到很多人在机考里翻车并不是因为代码逻辑而是栽在下面这些看起来很不起眼的细节上。4.1 “全配对”和“能配就配”是两种题目如果题目要求全员配对那么一旦相邻配对中出现差值大于K的情况就要输出-1。但如果题目只是问“最多能配成多少对”或者“在配对数最多的前提下最小总和”就不存在输出-1这个分支要用DP。考试时先读题最后一句如果出现“无法完成全部组队时输出-1”这类描述就用贪心如果出现“最多能匹配多少对”这类描述就用DP。我见过最可惜的翻车案例是一位读者把全配对版本的代码提交到“最大配对版本”的题目上结果本该输出一个非负整数他却输出-1直接丢了一整道题的分。4.2 int溢出K和答案必须用64位很多人认为实力值不超过10的9次方int就够用但忘记答案是所有差值之和。N最大10万极端情况下答案可以达到5乘以10的13次方这早就超过int的最大值21亿了。Java里用longC里用long longGo里用int64JS里数字本身是双精度浮点10的13次方远小于2的53次方所以JS不用特别处理。只有Python完全没有这种顾虑。4.3 输入读取的多行陷阱机考平台的数据文件不会像样例那样规规矩矩一行放完。第二行可能因为平台显示或者数据生成器的原因被拆成多行甚至行尾还有空格。Python里如果只读一次input().split()数组长度小于N一运行就数组越界。我在实操中已经养成习惯不管题目描述怎么说先写一个能循环读取直到数组长度满足要求的输入模板这能在各种在线评测平台上省掉无数烦恼。Java的Scanner和C的cin天然按空白符读取不会因为换行出错但如果你在Java里用了nextLine()去读第二行就会因为第一行末尾的换行符读到空串需要格外小心。5. 如果题目变成“最多配对数优先”DP怎么写我在文章开头提到网上题解打架的问题。为了让你碰到变体题时不会发懵这节把另一个版本的解法也讲透。5.1 变体长什么样变体题通常这样描述有N个玩家每个玩家有一个实力值。现在希望从中选出若干对玩家进行对战每对玩家实力差不能超过K。请问在配对数最多的情况下所有配对实力差总和的最小值是多少注意这里没有“必须用完所有玩家”N也可能不是偶数或者N是偶数但允许有人不参与对战。举个例子5 5 1 2 3 10 11最多能配出2对一种方案是(1,2)和(3,?)但10和11差1可以配对所以最多两对可以是(1,2)和(10,11)总和2。如果硬想配(1,2,?)是不行的因为三人不可能组成两对。所以输出2。5.2 DP状态设计仍然先排序。排序后定义两个数组pairCnt[i]表示前i个人排序后下标0到i-1能组成的最大对数minSum[i]表示在前i个人达到最大对数时的最小差值总和。初始化pairCnt[0] 0minSum[0] 0pairCnt[1] 0minSum[1] 0因为只有一个人时无法配对。从i2开始转移第i个人下标i-1有两种选择第一不参与配对。那么当前状态直接继承前i-1个人的状态pairCnt[i] pairCnt[i-1] minSum[i] minSum[i-1]第二和第i-1个人下标i-2配对。前提是a[i-1] - a[i-2] K配对后pairCnt[i] pairCnt[i-2] 1 candidateSum minSum[i-2] (a[i-1] - a[i-2])关键点在于比较如果配对后的对数比当前pairCnt[i]更大就更新如果对数一样大但候选总差值更小也更新。这就是“对数优先总和次之”的转移逻辑。5.3 Python核心代码def solve(): import sys input sys.stdin.readline n, k map(int, input().split()) a [] while len(a) n: a.extend(map(int, input().split())) a.sort() pair_cnt [0] * (n 1) min_sum [0] * (n 1) for i in range(2, n 1): # 默认第 i 个人不配对 pair_cnt[i] pair_cnt[i - 1] min_sum[i] min_sum[i - 1] diff a[i - 1] - a[i - 2] if diff k: cand_cnt pair_cnt[i - 2] 1 cand_sum min_sum[i - 2] diff if cand_cnt pair_cnt[i] or (cand_cnt pair_cnt[i] and cand_sum min_sum[i]): pair_cnt[i] cand_cnt min_sum[i] cand_sum print(min_sum[n]) solve()这段代码的思路和执行过程都很好理解。Go、Java、C、JS版本的DP无非是把数组替换成对应语言的语法核心转移完全一样考试时直接在之前的模板基础上改就行。5.4 为什么这种DP不能直接拿去做全配对版本因为DP允许有人落单。假设输入是[1, 100, 101, 200]K100。全配对版本里排序后相邻配对是(1,100)和(101,200)差值分别是99、99总和198合法。但DP版本可能选择让1和200落单只配(100,101)一对差值1因为“配对数最大”不要求全配对。调整到全配对约束下这个解就不成立了。所以考试第一步永远是确认题意要不要全员参与。要就贪心不要就DP。5.5 两个版本的差异对照判断维度全配对版本最大配对数版本N的奇偶性偶数可以为奇数是否存在输出-1存在不存在是否允许玩家落单不允许允许核心算法排序贪心排序动态规划状态设计不需要pairCnt/minSum数组典型复杂度O(N log N)O(N log N)6. 实战中的做题节奏与训练建议机考和平时刷题最大的不同在于你需要在有限时间内完成读题、编码、自测三道工序。我建议拿到题后按下面几步走。第一步先花30秒确认数据范围。看到N到10万基本可以排除暴力深搜和状态压缩DP。第二步确认配对约束。题目里出现“全部玩家都必须分成N/2组”直接切到贪心出现“尽可能多”“最多能组成几对”切到DP。第三步确认输出格式。要不要输出-1答案是不是整数都影响代码分支。第四步写完代码后在本地或者在线编辑器里至少跑三个测试用例一个常规样例、一个全无解样例、一个极限数据样例。极限数据不必真生成10万个数字可以把N改小但把答案规模撑大比如N4, K1000000000, 实力值1, 1000000000, 2000000000, 3000000000来验证数据类型的溢出问题。在平时训练上我建议多练几道同类经典题巩固这种感觉“最小化两两配对差值总和”“打家劫舍变体”“会议室安排”这类排序贪心或者排序DP的题刷上十道左右碰到“最佳对手”这类包装过的题目就会形成条件反射。多语言的话不用强求五种都精通。你只要把自己最熟的一门语言写到“不用过脑子就能敲出输入输出模板”的程度考试就成功了一大半。其余语言能看懂就行毕竟题解可能是别人用别的语言写的。我自己的习惯是Java和Python双修Java用来写正式代码Python用来快速验证思路。如果你用Go或者JS只要按本文的模板把输入输出背熟同样可以打得很稳。最后再分享一个小技巧。双机位考试的时候在线编辑器一般没有代码格式化功能也没有自动补全。我建议你在进考场之前把所有常用模板按语言分类整理到一个备忘录里提前背到肌肉记忆。考试开始后先花两分钟把输入输出骨架敲出来再填核心逻辑这样能显著降低紧张感。这道题本身不算难它考的不是你会不会用多高级的算法而是你能不能在一个看似唬人的题目名字下快速看穿它本质上只是一个排序问题。把这篇文章里的思路和代码吃透下次再碰到“最佳对手”你应该不会再慌了。