华为OD机试真题解析：篮球比赛分组问题的动态规划与多语言实现

1. 项目概述与核心价值最近在技术社区和求职圈里“华为OD机试”的热度一直居高不下尤其是随着2025年B卷真题的陆续流出很多准备冲刺OD岗位的朋友都在四处寻找高质量的真题解析和实战代码。今天我想以一个过来人的身份和大家深入聊聊其中一道非常经典的题目——“篮球比赛”。这道题不仅频繁出现在机试中其背后蕴含的算法思想更是面试官考察候选人逻辑思维和问题建模能力的绝佳素材。我自己在准备和带新人刷题的过程中发现很多朋友对这类“分组求最优”的问题感到棘手要么思路不清晰要么代码写出来又长又容易出错。所以这篇内容我会结合这道“篮球比赛”真题把它的来龙去脉、核心考点、多种解法的思路对比以及不同语言C、Java、Python、C、JS的实现细节掰开揉碎了讲清楚。无论你是正在备战华为OD还是单纯想提升自己的算法能力相信这篇超过5000字的深度解析都能给你带来实实在在的收获。简单来说“篮球比赛”这道题模拟了一个非常实际的场景你需要将10名球员分成两队每队5人使得两队的总能力值尽可能接近从而保证比赛的公平性。题目会给你一个包含10个整数的数组代表每位球员的能力值。你的任务就是找出一种分组方案使得两队总能力值之差的绝对值最小并输出这个最小的差值。这听起来像是一个组合优化问题直接暴力枚举所有分法理论上可行但效率极低。如何在有限的时间内机试通常对时间、空间复杂度有严格要求优雅地解决它就是我们需要攻克的核心。2. 题目深度解析与建模思路2.1 问题本质与抽象转化初次看到“篮球比赛”你可能会想“这不就是组合问题吗从10个里面选5个去A队剩下的去B队。”没错最直观的思路就是组合枚举。计算一下C(10,5)252种组合对于计算机来说似乎不算多。但在机试环境中这只是一个具体例子。如果题目泛化比如球员数量变为2n这个组合数会呈指数级增长C(2n, n)暴力枚举将立刻变得不可行。因此这道题的精髓在于引导我们寻找更高效的算法模型。我们仔细分析一下目标设所有球员能力值总和为total_sum我们选出5个人组成一队其能力值之和为sum_A那么另一队的能力值之和就是total_sum - sum_A。两队能力值之差的绝对值就是|sum_A - (total_sum - sum_A)| |2 * sum_A - total_sum|。我们的目标是让这个绝对值最小。这样一来问题就被巧妙地转化了我们需要从10个数中选出5个数使得这5个数的和尽可能接近total_sum / 2。因为当sum_A越接近total_sum/2时上面的差值公式结果就越小。这是一个典型的“从n个数中选k个数使其和最接近目标值”的问题是背包问题的一个变种更具体地说可以看作“二维费用背包”或“恰好选出k个数的子集和”问题。2.2 核心算法思路选型与对比明确了问题本质后我们来看看有哪些主流的解决思路并分析它们在机试场景下的优劣。思路一深度优先搜索DFS回溯这是最符合直觉的解法。我们通过递归尝试将每个球员“放入A队”或“不放入A队”并记录当前A队已选人数和当前能力值和。当已选人数达到5时计算当前方案下的差值并更新全局最小值。DFS需要遍历所有可能的组合其时间复杂度为 O(2^n)对于n102^101024看似比组合数252还多但因为加入了剪枝例如当已选人数超过5或未选人数不足以凑齐5人时提前返回实际搜索空间会小很多。这种方法的优点是思路直接代码易于理解和实现适合在时间紧迫的机试中快速写出一个可行解。缺点是当n变大时性能急剧下降。思路二动态规划DP这是更通用、更高效的解法。我们可以定义状态dp[i][j][k]表示从前i个球员中恰好选出j个人其能力值之和能否达到k。这是一个布尔型的DP。i的范围是0到10球员索引。j的范围是0到5需要选出的人数。k的范围是0到total_sum可能的能力值之和。 最终我们遍历所有k找到那些dp[10][5][k]为真的k计算|2*k - total_sum|取最小值即可。 动态规划的时间复杂度是 O(n * k * total_sum)其中n是人数k是需要选出的人数5total_sum是能力值总和。对于本题数据范围这个复杂度是可以接受的并且它具有很好的泛化能力。这是面试官最希望看到的能体现候选人扎实算法功底的解法。思路三排序后贪心有同学可能会想能不能先排序然后最大配最小这样来分组对于“分成两组和尽可能接近”的问题如果没有人数限制这近似于“数组分割问题”排序后按奇偶索引分是一种近似贪心。但本题有严格的“5人一队”限制贪心策略很容易失效。例如球员能力值为[1,1,1,1,1,100,100,100,100,100]总和是505一半是252.5。贪心从大的开始选可能会选出5个100和为500远远偏离目标。因此贪心算法对此题不适用必须使用搜索或动态规划来求精确解。注意在真实的华为OD机试中题目通常会给出明确的数据范围。如果球员数量就是10那么DFS是完全可以AC通过的。但如果题目描述中暗示或明示数据范围可能扩大比如“球员数量为偶数2n20”那么DP就是更稳妥、更显示水平的方案。在备考时两种思路最好都掌握。3. 多语言代码实现与细节剖析接下来我将分别用C、Java、Python、C语言和JavaScript五种语言实现基于动态规划的解法。选择DP是因为它更具普适性和教学意义。我会在代码中给出详细注释并对比不同语言实现时的细微差别和注意事项。3.1 C 实现兼顾效率与清晰度C在算法竞赛和机试中因其执行效率高而备受青睐。这里使用vector来实现三维DP表并注意空间优化。#include iostream #include vector #include algorithm #include cmath #include climits using namespace std; int main() { // 假设输入为10个整数这里用数组初始化模拟输入 vectorint ability {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // 示例数据 int n ability.size(); // n10 int k n / 2; // 每队需要k人即5人 int total_sum 0; for (int score : ability) total_sum score; // 动态规划数组 dp[j][s]: 能否恰好选j个人达到总能力值s // 因为i前i个人这个维度可以滚动掉所以我们用二维数组逆序更新 vectorvectorbool dp(k 1, vectorbool(total_sum 1, false)); dp[0][0] true; // 选0个人总和为0是可行的 for (int i 0; i n; i) { int current_ability ability[i]; // 必须逆序更新确保每个球员只被使用一次0-1背包 for (int j k; j 1; --j) { for (int s total_sum; s current_ability; --s) { if (dp[j - 1][s - current_ability]) { dp[j][s] true; } } } } int min_diff INT_MAX; // 遍历所有可能由5个人组成的和 for (int s 0; s total_sum; s) { if (dp[k][s]) { // 如果存在一种选5个人和为s的方案 int diff abs(2 * s - total_sum); if (diff min_diff) { min_diff diff; } } } cout 两队能力值最小差值为: min_diff endl; // 对于示例数据 {1...10}总和55最优解是选{1,4,6,9,10}和为30另一队和25差值为5。 // 输出应为 5 return 0; }C实现要点解析空间优化原始DP是三维dp[i][j][s]但我们发现状态转移只依赖于i-1层因此可以像0-1背包一样逆序更新二维数组dp[j][s]将空间复杂度从 O(n * k * total_sum) 优化到 O(k * total_sum)。逆序更新的原因这是0-1背包问题的核心技巧。正序更新会导致同一件物品被重复选取完全背包而逆序更新保证了每个球员的能力值在当前轮次只被考虑一次。数据类型能力值之和s可能很大但本题示例中总和不大用int足够。如果题目提示能力值很大可能需要使用long long。初始化dp[0][0] true是动态规划的起点表示不选任何人且和为0的状态是合法的。3.2 Java 实现注重工程严谨性Java的实现逻辑与C基本一致但使用ArrayList和数组有些许不同并且要注意输入输出的处理。import java.util.Scanner; public class BasketballGame { public static void main(String[] args) { Scanner scanner new Scanner(System.in); // 模拟输入10个能力值实际机试中需按题目要求读取 int[] ability {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int n ability.length; int k n / 2; // 每队5人 int totalSum 0; for (int score : ability) { totalSum score; } // dp[j][s]: 能否用j个人凑出总和s boolean[][] dp new boolean[k 1][totalSum 1]; dp[0][0] true; for (int i 0; i n; i) { int currentAbility ability[i]; // 逆序更新确保每个球员只用一次 for (int j k; j 1; j--) { // s需要从大到小遍历避免重复使用当前球员 for (int s totalSum; s currentAbility; s--) { if (dp[j - 1][s - currentAbility]) { dp[j][s] true; } } } } int minDiff Integer.MAX_VALUE; for (int s 0; s totalSum; s) { if (dp[k][s]) { int diff Math.abs(2 * s - totalSum); minDiff Math.min(minDiff, diff); } } System.out.println(两队能力值最小差值为: minDiff); scanner.close(); } }Java实现注意事项数组初始化Java中boolean数组默认值为false这正好符合我们的需求。输入处理机试真题通常需要从标准输入读取。这里用固定数组模拟实际代码中应替换为Scanner或BufferedReader读取。空间与性能Java中多维数组在堆上分配对于totalSum较大的情况要注意可能的内存限制。如果totalSum很大例如上万这个DP数组可能会占用较多内存。3.3 Python 实现突出简洁与表达力Python代码通常更短利用列表推导式和动态语言特性可以写得非常简洁但需要注意Python在循环较大数据时的性能。def min_ability_diff(abilities): n len(abilities) k n // 2 total_sum sum(abilities) # dp[j][s] 表示能否用j个人凑出总和s # 使用集合的集合来存储可能达到的和是一种更节省空间的方法但可能稍慢 # 这里为了清晰使用二维布尔列表 dp [[False] * (total_sum 1) for _ in range(k 1)] dp[0][0] True for ability in abilities: # 必须逆序更新 for j in range(k, 0, -1): for s in range(total_sum, ability - 1, -1): if dp[j - 1][s - ability]: dp[j][s] True min_diff float(inf) for s in range(total_sum 1): if dp[k][s]: diff abs(2 * s - total_sum) if diff min_diff: min_diff diff return min_diff if __name__ __main__: # 示例输入 abilities [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] result min_ability_diff(abilities) print(f两队能力值最小差值为: {result})Python实现技巧与坑点列表生成式初始化DP表[[False] * (total_sum 1) for _ in range(k 1)]是正确创建二维列表的方法。切忌使用[[False]*(total_sum1)]*(k1)这会导致内部列表是同一个对象的引用修改一个子列表会影响所有行。逆序循环range(k, 0, -1)和range(total_sum, ability - 1, -1)实现了逆序更新这是实现0-1背包DP的关键。性能考虑Python的循环较慢如果total_sum很大比如超过1000三层嵌套循环可能会成为性能瓶颈。在机试中Python解题要格外注意时间复杂度优先选择数学优化或更高效的算法。3.4 C语言 实现追求极致的控制与效率C语言实现需要手动管理内存代码稍长但能让你对底层有更深的理解并且在资源限制严格的环境下表现最佳。#include stdio.h #include stdlib.h #include stdbool.h #include limits.h #include math.h int main() { int abilities[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int n sizeof(abilities) / sizeof(abilities[0]); int k n / 2; int total_sum 0; for (int i 0; i n; i) total_sum abilities[i]; // 动态分配二维DP数组 dp[k1][total_sum1] bool **dp (bool **)malloc((k 1) * sizeof(bool *)); for (int i 0; i k; i) { dp[i] (bool *)malloc((total_sum 1) * sizeof(bool)); for (int j 0; j total_sum; j) { dp[i][j] false; } } dp[0][0] true; // DP过程 for (int i 0; i n; i) { int current_ability abilities[i]; for (int j k; j 1; j--) { for (int s total_sum; s current_ability; s--) { if (dp[j - 1][s - current_ability]) { dp[j][s] true; } } } } // 寻找最小差值 int min_diff INT_MAX; for (int s 0; s total_sum; s) { if (dp[k][s]) { int diff abs(2 * s - total_sum); if (diff min_diff) min_diff diff; } } printf(两队能力值最小差值为: %d\n, min_diff); // 释放动态分配的内存 for (int i 0; i k; i) free(dp[i]); free(dp); return 0; }C语言实现关键点动态内存分配由于total_sum是运行时计算的DP数组大小不确定必须使用malloc动态分配。务必记得最后要free释放内存防止内存泄漏。布尔类型C语言没有内置的bool类型C99以后有stdbool.h我们使用#include stdbool.h来使用bool、true、false。数组初始化动态分配的数组不会自动初始化必须用循环手动设置为false。效率优势C语言的数组操作和循环效率极高在处理大规模数据时优势明显。但代码复杂度也更高在机试中要权衡开发时间和运行效率。3.5 JavaScript (Node.js) 实现适配前端或Node环境华为OD的机试环境也可能支持JavaScript。这里提供Node.js版本的实现注意JS中数组的处理方式。function minAbilityDiff(abilities) { const n abilities.length; const k Math.floor(n / 2); const totalSum abilities.reduce((sum, val) sum val, 0); // 创建二维DP数组初始化为false const dp Array.from({ length: k 1 }, () new Array(totalSum 1).fill(false)); dp[0][0] true; for (const ability of abilities) { // 逆序更新 for (let j k; j 1; j--) { // 注意s需要从大到小遍历这里用for循环控制 for (let s totalSum; s ability; s--) { if (dp[j - 1][s - ability]) { dp[j][s] true; } } } } let minDiff Infinity; for (let s 0; s totalSum; s) { if (dp[k][s]) { const diff Math.abs(2 * s - totalSum); minDiff Math.min(minDiff, diff); } } return minDiff; } // 示例 const abilities [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; const result minAbilityDiff(abilities); console.log(两队能力值最小差值为: ${result});JavaScript实现细节数组创建与填充使用Array.from和fill方法是创建并初始化二维数组的简洁写法。Array.from({ length: k1 }, () new Array(totalSum1).fill(false))创建了一个(k1) x (totalSum1)的矩阵并全部填充为false。逆序循环JS的for循环可以方便地实现逆序。注意循环变量要用let声明。性能提醒在V8引擎中访问多维数组dp[j][s]的性能尚可但如果totalSum非常大创建这么大的二维数组可能会消耗大量内存。在实际机试中要留意题目给定的数据范围。4. 算法优化与边界情况探讨4.1 动态规划的进一步优化我们上面实现的DP空间复杂度是 O(k * total_sum)。如果total_sum很大比如能力值都是几百上千这个数组可能会非常大。有没有优化空间呢优化思路使用位运算Bitset优化对于布尔型DP我们可以用整数的每一个二进制位来表示某个和s是否可达。例如用一个long long类型的变量bitset如果第s位是1表示当前状态下总和s是可达的。 对于“选j个人”这个维度我们可以维护一个数组bitset[j]每个元素是一个整数或bitset表示选j个人时所有可能达到的和的集合。 状态转移时bitset[j] | (bitset[j-1] ability)。这表示在上一状态选了j-1个人所有可能和的基础上加上当前球员的能力值ability相当于左移就得到了新的可能和然后与当前状态取或。这种优化可以将时间复杂度中的total_sum因子降低到total_sum / wordsize通常是64空间占用也大大减少。在C中可以使用bitset或手动进行位运算。这对于total_sum在几千以内的题目效果显著。// C Bitset优化示例核心部分 #include bitset const int MAX_SUM 1000; // 假设总和不超过1000 vectorbitsetMAX_SUM1 dp(k1); dp[0][0] 1; for (int ability : abilities) { for (int j k; j 1; --j) { dp[j] | (dp[j-1] ability); } } // 然后遍历 dp[k] 中所有为1的位计算最小差值4.2 边界条件与异常处理在实现时我们必须考虑一些边界情况以确保程序的健壮性输入数据合法性题目保证输入是10个正整数吗是否需要处理非正整数、浮点数通常不会在实际编码时如果从标准输入读取要确保解析正确。总和为奇数/偶数总和total_sum可能是奇数那么total_sum / 2就不是整数。我们的算法目标是让sum_A接近total_sum/2并不要求相等所以不影响。无解情况理论上只要k n总是有解的至少可以选出k个人。但在更一般的“选k个数和最接近target”问题中如果所有数都大于target可能无解。本题中target是total_sum/2且都是正数所以一定有解。大数据范围如果能力值很大或人数很多total_sum会很大导致DP数组超大。这时需要评估是否能用bitset优化或者题目是否暗示了其他特性如能力值范围很小可以利用。4.3 测试用例设计自己设计测试用例是验证代码正确性的关键。针对“篮球比赛”你应该覆盖以下场景基础用例[1,2,3,4,5,6,7,8,9,10]预期结果5。极端平衡[5,5,5,5,5,5,5,5,5,5]总和50任意分两队和都是25差值0。极端不平衡[1,1,1,1,1,100,100,100,100,100]总和505。最优解是一队5个1和5另一队5个100和500差值495不对这样差值太大了。实际上最优解应该是尽可能均衡比如一队选4个100和1个1和401另一队选1个100和4个1和104差值297。或者用DP计算。包含重复值[2,2,2,2,2,3,3,3,3,3]总和25。理想情况一队和12另一队和13差值1。看看算法能否找到。最小规模如果题目泛化n2, k1。那么就是两个数差值就是两者差的绝对值。5. 机试实战技巧与备考建议5.1 如何快速识别此类问题在华为OD或其他公司的机试中题目描述千变万化但核心考点往往就那几个。“篮球比赛”属于“划分问题”或“带限制的子集和问题”。当你看到类似“分成两组使得...之差最小”、“选出k个数使其和最接近某个值”、“公平分配”等关键词时就要立刻联想到动态规划或深度优先搜索。关键特征提取有一个集合数组、列表。需要从中选出一个子集子集有数量限制如恰好k个。目标是最优化某个指标如和尽可能接近目标、差最小。 符合这些特征大概率就是背包DP或DFS回溯的变体。5.2 机试编码时间分配与策略华为OD机试通常时间紧张一般2-3道题共90-150分钟。面对“篮球比赛”这类中等难度的题目建议按以下节奏进行前5分钟仔细阅读题目理解输入输出格式、数据范围、边界条件。用笔在纸上画一画抽象出问题模型。这一步绝对不能省理解偏差会导致全盘皆输。5-10分钟确定算法思路。如果数据范围小如n20DFS剪枝是快速出答案的捷径。如果数据范围中等或较大果断选择动态规划。在脑海里或草稿纸上画出状态转移方程。20-30分钟编码实现。选择你最熟悉的语言按照确定的思路编写。先写出核心算法函数确保逻辑正确。变量命名清晰关键步骤加上注释。5-10分钟测试与调试。用你之前设计的几个典型测试用例包括边界情况进行测试。在本地IDE或心理模拟运行检查输出是否符合预期。最后5分钟提交前复查。检查输入读取、输出格式是否完全符合题目要求比如末尾换行、空格等。确认没有低级错误如数组越界、初始化错误。5.3 关于使用编程语言的选择从热搜词可以看出C和Java是华为OD机试的热门语言。我的建议是C执行效率最高STL库强大vector, bitset, algorithm等适合对性能要求高的题目。但指针和内存管理需要小心。Java语法严谨生态成熟有大厂的工程背景。在机试中其速度也完全足够。对于数据结构类题目Collections框架很好用。Python语法简洁开发速度快适合快速验证思路。但在处理大量循环和递归时性能是短板有些题目可能会卡时间。C更底层控制力强但在机试中编码效率较低除非你特别熟练否则不推荐。JavaScript如果机试环境支持Node.js且你前端背景深厚可以选择。但要注意其异步特性在算法题中一般用不到且性能通常不如C/Java。选择你最熟悉、编码速度最快、调试最顺手的一门语言并坚持用它刷题。5.4 从“篮球比赛”延伸出的常见变体题掌握了一道题的解法要能做到举一反三。与“篮球比赛”同源或类似的机试题还有很多例如分割等和子集给定一个数组判断是否能分成两个和相等的子集LeetCode 416。这是“篮球比赛”的无人数限制版本可以用0-1背包的DP解。目标和给定一个数组和一个目标数给每个数添加或-使得表达式等于目标数LeetCode 494。可以转化为子集和问题。最接近目标值的子序列和从数组中选若干数使其和最接近目标值但无人数限制。可以用DP或折半搜索。公平分队可能变成“分成两队使得两队最高能力值之差最小”或“使得两队平均能力值之差最小”核心建模思路类似但目标函数不同。备考时建议在刷完一道题后主动去搜索和练习它的变体形成知识网络这样在考场上才能灵活应变。6. 常见错误与调试心得在我自己刷题和辅导他人的过程中发现了一些高频错误点这里集中列出来希望大家能避开这些坑错误1DP数组初始化错误现象结果总是0或者一个不正确的固定值。根因忘记初始化dp[0][0] true。这是所有DP的起点没有这个状态后续所有状态都无法转移过来。检查在DP循环开始前打印一下dp数组的初始状态确保dp[0][0]是正确的。错误2更新顺序错误导致物品重复使用现象在“恰好选k个”的限制下结果却比预期多好像一个人被用了多次。根因在更新dp[j][s]时j和s的循环是正序的。这会导致在考虑第i个球员时dp[j][s]可能由本轮刚刚更新过的dp[j-1][s-ability]转移而来相当于第i个球员被使用了多次。解决牢记0-1背包逆序更新的原则。对于“人数”和“容量”这两个维度在遍历到当前球员时都必须从大到小逆序遍历。错误3误解题意输出格式错误现象算法逻辑正确但提交后判题系统返回“输出错误”而非“答案错误”。根因没有严格按照题目要求的格式输出。例如题目要求输出“最小差值”你却输出了“最小差值对应的两队和”。或者要求输出一个整数你却带了多余的文字说明。教训机试判题通常是严格比对输出。务必仔细阅读题目中的“输出描述”部分复制样例输出的格式最好在代码最后只用一句cout min_diff;或System.out.println(min_diff);。错误4忽略大数据范围导致的溢出或超时现象在小数据测试通过提交后遇到大数据就“运行错误”或“超时”。根因溢出total_sum可能很大用int存储会溢出应使用long long。超时使用了未剪枝的DFS或者DP的三重循环在数据量大时太慢。应对在编写代码前根据题目给出的数据范围如1 ability[i] 1000, 2 n 20估算一下total_sum的最大值1000*2020000和DP数组大小21 * 20001判断是否在可接受范围内。如果n更大比如50total_sum也更大就需要考虑bitset优化或折半搜索等更高级的技巧。调试心得 当你的代码结果不对时不要慌张。可以尝试以下步骤小数据人脑模拟用一个最简单的例子比如3个数[1,2,3]k1。手动推导DP表然后单步调试你的程序对比每一步的DP状态是否一致。打印中间状态在DP循环中关键步骤后打印出dp数组或bitset的状态看看转移是否符合预期。对比暴力解对于小数据n10写一个DFS暴力枚举所有组合计算出正确答案。然后用你的DP程序跑同样的数据对比结果。这是验证算法正确性的黄金标准。利用在线判题平台的调试功能很多平台如牛客、力扣提供用例错误时的输入输出对比。仔细分析第一个出错的用例往往能发现逻辑漏洞。最后算法学习没有捷径唯手熟尔。“篮球比赛”这道题就像一个经典的模版吃透了它你就掌握了解决一大类划分问题的钥匙。在备战华为OD或其他技术面试时建议将这道题以及它的各种变体反复练习直到你能在15分钟内无bug地写出DP解法。当你对状态定义、转移方程、优化技巧都了然于胸时面对考场上的新题你才能从容不迫快速找到破解之道。