华为OD机考的C卷题库里“游戏分组”是一道出场率相当高的题。不少人觉得它简单真上了双机位考场才发现一个空格就能导致判错、一个类名不对直接0分、一行调试输出就把整道题搭进去。这篇文章不打算只给一份能跑的代码而是把Java、Python、JS、C/C、Go五种语言的完整解法都整理出来顺带把机考的ACM输入模式、边界条件、容易翻车的细节逐个拆开说清楚。无论你是刚开始刷题的应届生还是想突击转岗的社招选手花二十分钟把这道题吃透收益比盲目刷十道简单题大得多。1. C卷“游戏分组”原题拆解10个人、两组5人、差值最小1.1 题面还原与考试形式先还原一下题面。部门准备组织团建游戏10个人分成两组进行对抗每组5人。每个人的能力值已经提前打过分现在要设计一种分组方案让两边的能力值总和尽可能接近最后输出这个最小差值。输入格式一行10个空格分隔的正整数代表10个人的能力值。 输出格式一个整数表示两组能力值总和的最小差值。示例 输入1 2 3 4 5 6 7 8 9 10 输出1解释一种最优分组是{1,2,7,8,9}和{3,4,5,6,10}两组能力值总和分别是27和28差值为1。这两组无论怎么交换成员都不可能让差值变成0所以答案就是1。华为OD机考采用的是ACM模式也就是需要自己编写完整的输入输出处理而不是像某些刷题网站那样只填一个函数体。C卷是当前题库的一个版本考试时从题库里随机抽题所以“游戏分组”这道题被抽中的概率不低。考试使用双机位一台电脑用来答题另一台手机或者平板从侧后方架起来确保考试过程全程可见。双机位本身不会影响代码逻辑但会影响心态——平时习惯了在IDE里反复调试考场上就要求一遍过所以输入输出这些“跟算法关系不大”的环节恰恰是拉开分数差距的地方。1.2 考点拆解这道题真正在考什么先别看解法想想出题人为什么要选这道题。第一它在考组合枚举。10个人的分组方案总数是C(10,5) 252种。这个规模小到可以暴力枚举不需要任何高级数据结构。第二它在考最值维护。枚举过程中要不断记录当前最小差值并且在所有方案中选出最优的。第三它在考ACM模式的完整闭环。思路简单但要在考场环境下一次写对并不容易。我见过太多人挂在细节上Java的类名不叫MainGo用了math.Abs忘记转intJS的readline没处理换行符Python的input()遇到多行输入直接报错。这些都是这道题真正在考察的非算法能力。换句话说这是一道典型的“思路两分钟写代码十分钟调试半小时”的题。它不考你懂多少算法考的是你在限定时间内能不能稳定输出。1.3 规模预判为什么C(10,5)小到不用优化10个人选5个进入第一组剩下5个人自动组成第二组。组合数是252就算把每条递归路径完整展开叶子节点也只有252个。算上递归过程中产生的中间状态总量也在千级任何语言跑起来都是毫秒级。所以这道题的策略非常明确不要上花哨的优化技巧用最笨、最直接、最不可能写错的方式去解。把力气花在把输入输出写稳上比任何剪枝优化都重要。很多人一看到“差值最小”就想到动态规划看到“组合”就想到状态压缩实际上在这个数据规模下直接枚举就是最优解。2. 两种主流解法DFS枚举与01背包变体2.1 DFS回溯把“每个元素选或不选”穷举清楚DFS是这道题的首选解法原因就一个好写、难错。按数组下标从小到大遍历每个人递归函数需要维护三个状态idx当前处理到第几个人。count第一组已经选了几个人。sum第一组的能力值之和。当count等于5时第一组选满第二组自动确定此时差值就是abs(total - 2 * sum)。total是10个人能力值的总和第二组的和就是total - sum。递归过程中每个人有两种选择进第一组或者不进第一组。这两种选择都继续递归最终就覆盖了全部252种组合。剪枝只需要一条如果剩下的元素个数不够补满5个人直接返回也就是10 - idx 5 - count时剪掉。这个剪枝能砍掉大量无效分支让递归树的规模进一步缩小。这个枚举方式可以用排队分水果来类比每个人面前只有两个动作拿或者不拿拿满5个就结算剩下的水果自动归另一边。整个过程不重不漏逻辑非常直白。2.2 01背包变体把“组和”变成“凑数”问题如果不想写递归可以用01背包的思路来解。把目标翻译一下从10个数里选5个数让它们的和尽量接近total / 2。定义一个布尔数组dp[c][s]表示“从已遍历的元素中选c个数能否凑出总和s”。遍历每个数时按“每个数只能用一次”的规则倒序更新selected 从 5 到 1 s 从 total 到 v-1 如果 dp[selected-1][s-v] 为 True dp[selected][s] True初始化dp[0][0] True。最后在所有dp[5][s]为True的s里找abs(total - 2 * s)最小的那个就是答案。这个解法的关键在倒序遍历。如果正序遍历同一个数会被重复使用多次那就从01背包变成完全背包了。初学者经常在这里翻车而且一旦数组维度和更新方向写错样例大概率全过提交却超时或者答案错误。不过说实话这道题的数据范围决定了DFS已经足够DP反而要开一个(total 1) * 6的布尔数组总和大一点就会额外消耗内存和循环时间。所以我的建议是首选DFSDP可以写一遍用来加深理解但考场上没必要冒险。2.3 位运算枚举另一种写起来很爽的暴力第三种解法给喜欢简洁写法的人用二进制掩码枚举所有10位状态某一位是1就代表这个人进第一组。def min_diff_by_bit(nums): n len(nums) total sum(nums) ans total for mask in range(1 n): if mask.bit_count() ! n // 2: continue s 0 for i in range(n): if (mask i) 1: s nums[i] ans min(ans, abs(total - 2 * s)) return ansPython里mask.bit_count()可以直接数二进制中1的个数C对应的是__builtin_popcount(mask)。一共1024个状态每个状态最多数10位性能同样没有问题。位运算解法的代码量比DFS更短但可读性差一些适合在函数式编程手感比较强的语言里使用。2.4 三种解法复杂度对比解法时间复杂度空间复杂度写错风险推荐指数DFS枚举O(C(10,5))约252个叶子节点O(10)递归栈低五星01背包变体O(5 * total)total最大10万O(6 * total)中容易正序写错四星位运算枚举O(2^10 * 10)O(1)低但可读性一般四星从稳定性角度出发考场上我强烈建议使用DFS。剩下的时间可以用来检查输入输出是否规范这比在代码里加一堆优化要有价值得多。3. 五种语言的完整实现能直接上手的版本3.1 Java类名和Scanner是你唯一的坎Java在OD机考中有一个硬性要求主类必须叫Main且不能带package声明。我用Scanner读取10个整数一次读完。递归方法做成static因为main是static直接调用最方便。import java.util.Scanner; public class Main { static int[] a new int[10]; static int total 0; static int minDiff Integer.MAX_VALUE; public static void main(String[] args) { Scanner sc new Scanner(System.in); for (int i 0; i 10; i) { a[i] sc.nextInt(); total a[i]; } dfs(0, 0, 0); System.out.println(minDiff); } static void dfs(int idx, int count, int sum) { if (count 5) { int diff Math.abs(total - 2 * sum); if (diff minDiff) { minDiff diff; } return; } if (idx 10) { return; } if (10 - idx 5 - count) { return; } dfs(idx 1, count 1, sum a[idx]); dfs(idx 1, count, sum); } }这里有几个地方要特别注意。第一Math.abs(total - 2 * sum)不会溢出。能力值范围通常是[1, 10000]10个加起来最多100000int完全够用。但如果题目没给范围稳妥起见可以声明成long。第二剪枝放在count 5的判断之后。很多人喜欢把剪枝写在入口处看起来也没问题但要注意别把idx 10和剪枝顺序搞反否则会漏掉count刚好等于5时还没来得及更新的情况。第三全局变量直接使用static声明就行但不要在递归方法内部重新声明一个同名局部变量否则你会疯狂怀疑人生。3.2 Python全局变量用list包一层更稳Python的代码量最小但有两个常见的坑值得提前说。第一个是global的声明问题如果直接在dfs里给min_diff赋值必须先声明global min_diff否则Python会认为你新建了一个局部变量。为了避免这个麻烦我用一个长度为1的列表min_diff [total]闭包里修改min_diff[0]完全不会碰到作用域问题。第二个是输入读取如果题目输入里恰好只有一行10个数字用sys.stdin.readline()是可以的但用sys.stdin.read()统一读进来再split()更稳这样不管输入是一行还是多行都不会挂。import sys def main(): data list(map(int, sys.stdin.read().split())) nums data[:10] total sum(nums) min_diff [total] def dfs(idx, cnt, cur_sum): if cnt 5: diff abs(total - 2 * cur_sum) if diff min_diff[0]: min_diff[0] diff return if idx 10: return if 10 - idx 5 - cnt: return dfs(idx 1, cnt 1, cur_sum nums[idx]) dfs(idx 1, cnt, cur_sum) dfs(0, 0, 0) print(min_diff[0]) if __name__ __main__: main()这段代码里我把剪枝、边界、更新答案的顺序固定为先判断是否选满5人再判断是否越界最后判断剩余元素是否够用。这个顺序是有讲究的。如果把剪枝放在最前面一旦idx正好等于10但count也等于5答案就永远不会被更新。Python递归深度在这里只有10层完全不用担心栈溢出问题。有些人会把这类递归写成迭代完全没有必要。3.3 JavaScriptOD机考的JS不是浏览器里的JS很多前端同学习惯写浏览器里的JavaScript一到机考环境就懵没有document没有window也没有全局alert。OD机考的JS是Node.js环境需要自己从标准输入读数据。下面这份代码用process.stdin的data/end事件流比readline更抗造不管输入有多少空行、多少连续空格都能一次解析完。const process require(process); let input ; process.stdin.on(data, chunk { input chunk; }); process.stdin.on(end, () { const nums input.trim().split(/\s/).map(Number); const total nums.reduce((acc, cur) acc cur, 0); let minDiff Number.MAX_SAFE_INTEGER; function dfs(idx, count, sum) { if (count 5) { const diff Math.abs(total - 2 * sum); if (diff minDiff) minDiff diff; return; } if (idx 10) return; if (10 - idx 5 - count) return; dfs(idx 1, count 1, sum nums[idx]); dfs(idx 1, count, sum); } dfs(0, 0, 0); console.log(minDiff); });这里的关键是split(/\s/)而不是split( )。机考输入里可能出现多个连续空格、制表符、甚至行尾换行正则\s能匹配所有空白字符一次处理干净。Number.MAX_SAFE_INTEGER作为初始最大值也够用因为这道题的答案不会超过10万。递归函数定义在事件回调里通过闭包引用nums、total和minDiff这是Node.js里很自然的做法。注意别用浏览器里才有的window.Math或者global.parseInt之类的写法Node.js的全局对象是global但这里完全用不到。3.4 C/C头文件别偷懒abs注意类型C/C在这道题上优势很明显代码短、运行快、cin/cout处理10个数毫无压力。但有三个点我见过好几个人翻车。第一bits/stdc.h是GCC的万能头文件多数在线评测环境支持但个别严格要求标准头文件的环境会编译失败。建议直接用#include iostream、#include cstdlib、#include climits不依赖万能头文件更稳。第二abs()在C里对int和long long都有重载。这道题用int没问题但如果你把total或sum声明成long long就要用llabs()否则可能得到错误结果。第三ios::sync_with_stdio(false);和cin.tie(nullptr);能加快输入输出虽然对这道题可有可无但写上没坏处还能展示你对性能细节有意识。#include iostream #include cstdlib #include climits using namespace std; int a[10]; int total 0; int minDiff INT_MAX; void dfs(int idx, int cnt, int sum) { if (cnt 5) { minDiff min(minDiff, abs(total - 2 * sum)); return; } if (idx 10) return; if (10 - idx 5 - cnt) return; dfs(idx 1, cnt 1, sum a[idx]); dfs(idx 1, cnt, sum); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); for (int i 0; i 10; i) { cin a[i]; total a[i]; } dfs(0, 0, 0); cout minDiff endl; return 0; }INT_MAX来自climits如果你只用iostream而忘了这个头文件在某些环境下会编译报错。全局数组默认初始化为0这里反正会在main里逐项赋值所以不用显式初始化。3.5 Go没有内置absmath.Abs要转floatGo的坑比较特殊标准库里没有int类型的abs函数只有一个math.Abs而且入参和返回值都是float64。所以写绝对值时必须写成int(math.Abs(float64(total - 2*sum)))少一步转换就会编译报错。输入方面bufio.Scanner读入一行然后用strings.Fields按任意空白字符切分比手动按空格split更健壮会自动处理多个连续空格。strconv.Atoi的第二个返回值是错误这里可以忽略因为机考输入一定是合法整数。package main import ( bufio fmt os strconv strings ) var nums []int var total int var minDiff int func dfs(idx, cnt, sum int) { if cnt 5 { diff : int(math.Abs(float64(total - 2*sum))) if diff minDiff { minDiff diff } return } if idx 10 { return } if 10-idx 5-cnt { return } dfs(idx1, cnt1, sumnums[idx]) dfs(idx1, cnt, sum) } func main() { scanner : bufio.NewScanner(os.Stdin) scanner.Scan() parts : strings.Fields(scanner.Text()) nums make([]int, len(parts)) for i, p : range parts { v, _ : strconv.Atoi(p) nums[i] v total v } minDiff total dfs(0, 0, 0) fmt.Println(minDiff) }注意这里minDiff初始化为total。因为每个人能力值都是正整数任何一组5人的和最小也有5另一组最多total - 5差值一定小于total。所以用total作为初始最大值是安全的。不要用math.MaxInt32虽然Go的math包里确实有这些常量但不同版本和平台下int的位数可能不同直接用total初始化反而更简单可靠。bufio.Scanner默认的token大小限制是64KB本题输入只有一行远远够用。如果遇到过万的长文本输入需要调整scanner.Buffer但这道题完全不需要。4. 双机位考场上最容易翻车的四个细节4.1 输入不是你想的那么干净机考输入看起来是“一行空格分隔”但实际评测时可能包含换行、多余空格、甚至制表符。如果你用scanner.nextInt()或者cin int这种“自动跳过空白”的API其实没问题但如果你用readline().split( )严格按单个空格切就可能在多个连续空格或换行时踩坑。各语言推荐写法JavaScanner默认用空白符做分隔符直接nextInt()即可。Python用sys.stdin.read().split()自动适配任意空白。JavaScript用split(/\s/)不要用split( )。Go用strings.Fields。C/Ccin 天然跳过空白。这几个写法我都有过教训。最早我写JS题时习惯split( )本地测试一切正常提交后偶发报错就是因为评测数据里有一个\r字符或者多个连续空格。4.2 分组不区分先后别把方案数翻倍10个人分两组每组5人。第一组选了{1,2,3,4,5}另一组自动就是{6,7,8,9,10}。如果你在递归里把“谁进第一组”和“谁进第二组”当成两件事枚举方案数会翻倍但最终算出的最小差值还是相同的——因为差值取了绝对值A组和B组完全对称。翻倍不会导致答案错误只会浪费一点时间。真正要小心的是输出。差值取abs(total - 2 * sum)后就是最终答案不需要再除以2。曾经有人在备考群里问为什么自己的答案是标准答案的两倍就是拿差值再去做了对称处理反而搞错了。4.3 多打印一行调试信息整题0分ACM模式严格比对标准输出。很多人在本地IDE跑通了代码里留着System.out.println(sum sum)或者printf(debug...)之类的调试语句考场上忘记删。评测系统拿到输出后发现多了不该有的行直接判0分。这个错误离谱但高频。我的习惯是写完代码先自查所有输出语句凡是System.out.println、print、console.log、fmt.Println、cout逐行确认是不是最终答案。一条printf只保留最后一行其他全部删掉。4.4 样例通过率100%但实际0分的隐藏原因还有一种更隐蔽的情况样例跑通了提交却是0分。除了调试输出之外常见原因还有这几类Java类名不是Main或者写了package声明。文件名和类名不一致OD平台一般只认Main.java。JS代码里用了浏览器API比如window、document在Node.js环境根本不存在。Go的package不是main或者缺少func main()入口函数。C代码用了当前编译标准不支持的特性。Python代码写在if __name__ __main__:外面导致模块导入时也执行了主逻辑。这类问题在自己电脑上完全暴露不出来只有提交到评测机才会出问题。建议考试前先用平台的在线自测功能跑一遍空模板确认环境正常再开始写题。5. 从“游戏分组”延伸出去组合枚举题的通用解法和备考思路5.1 一套能套用多数组合枚举题的DFS模板这道题的DFS代码非常典型可以抽象成一套通用模板从n个元素里选k个使某个目标函数最优。核心参数只有两个当前下标和已选个数。def dfs(idx, chosen, state): if chosen k: update_answer(state) return if idx n: return if n - idx k - chosen: return dfs(idx 1, chosen 1, state nums[idx]) # 选当前元素 dfs(idx 1, chosen, state) # 不选当前元素这套模板可以套到很多100分题上比如从n个数里选k个使和最大或最小、判断能否凑出某个目标值、简单子集划分问题。核心就是保证“不重不漏”地遍历所有组合。我在实际刷题中会把这道模板题重复写三遍以上每一遍都默写直到完全不用思考就能落下每个括号和缩进。考场上心态紧张的时候肌肉记忆比临场推理可靠得多。5.2 如果人数不是10而是30怎么办这道题固定10人所以DFS是标准答案。但如果遇到变体比如n30选15C(30,15)超过1.5亿DFS会直接超时。那时候需要折半枚举的思路把30个人分成两半各自枚举所有可能的选中组合和组和再用哈希表匹配两半的信息找到最接近total/2的组合。复杂度从组合数级别降到大规模枚举级别。不过这种进阶思路在OD机考的100分题上一般用不到。200分题如果遇到“两个集合尽量接近”的问题可以留作备用方案。先把基础模板写对再考虑优化。5.3 机考时间分配和语言模板准备最后聊点实际的备考经验。OD机考的题目结构一般是两道100分题加一道200分题总时长基本在150分钟左右。我的建议是前40分钟先把两道100分题都读一遍挑最有把握的先做确保稳定拿到100分。第二道100分题哪怕暂时没思路也先把暴力解法写出来拿部分分。最后80分钟攻200分题优先写暴力回溯和简单DP不要一上来就追求最优解。语言模板方面每种语言准备一份“输入输出模板”非常重要。Java就记住Main类和Scanner模板Python就记住sys.stdin.read().split()模板JS就记住process.stdin事件流模板Go就记住bufio.Scanner模板C就记住cin 模板。把这些模板背熟考试时10秒内能搭出框架剩下的精力全放在算法上。如果你正在准备机考我的建议是先把你要用的那种语言写熟再把其他语言版本的差异点过一遍。“游戏分组”是一个极其标准的组合枚举题它考察的不是算法天赋而是你在限定时间内把思路稳定落地的能力。把这道题吃透同类的高频题你都会顺很多。