窗外下着雨我正对着考试系统里那道“部门人力分配”发呆。那是华为OD机考双机位C卷里让我印象最深的一道题——不是因为它难到没思路而是因为我第一次做的时候明明想到了二分答案却卡在了检查函数的边界细节上白丢了二十分。后来我把这题的 Python、Java、JS、C、Go 五个版本全写了一遍又用几组刁钻用例反复验证才算彻底摸清了它的脾气。今天把这套完整的心得写下来希望能帮你少走点弯路。全文围绕机考环境、题目拆解、二分思路、贪心检查函数、五语言实现和实战避坑六个部分展开适合准备华为OD机考、或者在补二分答案专题的读者直接参考。1. 双机位考场下先把这套流程踩顺再说算法1.1 双机位到底在查什么华为OD机考是远程线上考试所谓双机位简单说就是两个摄像头同时盯着你第一机位是电脑自带的摄像头需要拍到你的正脸、双手和屏幕第二机位是手机摄像头放在身体侧后方约一米的位置需要拍到你整个桌面、键盘和电脑屏幕。手机要求用支架固定不能用手持也不能中途拿起来看消息。我考那次最麻烦的不是题目而是调机位角度。电脑摄像头拍不到键盘侧面手机支架又不够高侧面画面里有一块屏幕反光看不清。折腾了快二十分钟才通过环境检测等真正坐到代码编辑器前面时心态已经有点绷了。所以我的第一个建议是提前一天把设备调好考试当天只做二次确认别把时间浪费在摆摄像头上。1.2 机考系统里容易被忽略的硬约束机考系统通常用浏览器打开要求用 Chrome 或指定内核的浏览器进系统前会做摄像头和网络检测。答题时你面对的是一个不带智能补全的在线编辑器代码靠手动输入运行后拿到输出再提交判题。有些同学平时用惯了 IDEA 的自动导包、自动补全到了考场连 Scanner 头文件都要默写这块需要提前适应。另一个容易被忽略的点是切屏。系统对切屏次数非常敏感切出去复制材料或者查资料会被记录并可能触发警告。我认识的一个人因为频繁切屏直接被判违纪成绩作废。所以考试期间把微信、浏览器无关标签页全部关掉手机静音放远一点别做多余动作。还有一点机考是 ACM 模式也就是你要自己处理输入输出不是只写一个函数。这意味着你在牛客网刷题时积累的“只填核心代码”习惯到考场里必须切换成完整的 main 标准输入解析。2. “部门人力分配”原题拆解连续分组的最大和最小化2.1 我记忆中的原题长这样题目大意是有 n 个开发人员每个人的产出值用一个整数表示这些开发人员只能按顺序分配到不同的部门里每个部门拿到的是一个连续的人数列。现在给定部门数量 m要求把 n 个人全部分完使得所有部门中产出总和最大的那个值尽可能小。输出这个最小化的最大值。这类题本质上是“把一个数组切成 m 段连续子数组让所有子数组和的最大值最小”。注意关键词“连续”——人员不能重排部门拿到的人一定是紧挨着的一段。这一点非常关键很多人在考场上把它理解成了随便把人分组甚至试图用组合数学去穷举方向就错了。输入输出格式大致是这样的2 3 5 10 4第一行是部门数 m第二行是人数 n第三行是 n 个整数。输出一个整数表示最优分配下最大部门产出的最小值。对于上面的样例把 {5} 分给部门一{10, 4} 分给部门二最大产出是 14另一种切法是 {5, 10} 和 {4}最大产出是 15所以答案是 14。2.2 输入输出里必须抠的三个细节数据范围n 可能到 10 万甚至更大每个 ai 可能到 1e9 级别求和会超过 int。用 Java 的 long、C 的 long long 是稳妥的。输入顺序不同场次的题目可能把人数 n 放第一行、部门数 m 放第二行考场上一定先看样例别想当然。边界情况如果 m n每个人自己成组就行答案就是数组最大值如果 m 1整个数组一个部门答案就是数组总和。这两个极端用例最能检验你的检查函数写没写对。3. 暴力为什么不行二分答案的思路是怎么长出来的3.1 组合爆炸的暴力方案如果不知道“二分答案”这个套路第一反应可能是枚举所有切法。把 n 个人切成 m 段连续子数组本质是在 n-1 个间隙里选 m-1 个切点方案数是 C(n-1, m-1)。当 n 100000m 50000 时这个数字大到无法想象跑断服务器也算不完。退一步说就算用动态规划O(n²m) 的时间复杂度也过不了大数据。这时候要换一种思考方式我们不想知道“具体怎么切”只想知道“切出来后最大值最小能到多少”。它本身是一个优化目标而经典处理这类问题的工具之一就是二分答案。3.2 答案的单调性是二分的前提设一个猜测值 limit表示“我要求每个部门的最大产出不能超过 limit”。那么limit 越小越难满足需要的部门数就越多limit 越大越容易满足需要的部门数就越少。当 limit 大到整个数组的总和 sum 时一个部门就能装下全部人当然满足当 limit 小到数组最大值 max 时只要每个最大值都能独立成组也还有可能满足。所以答案一定落在区间 [max, sum] 之间并且这个区间里存在一个临界点小于它的 limit 不可行大于等于它的 limit 全部可行。这正是二分答案的标准形态。为什么不从 0 开始二分因为任何一段子数组的和至少包含其中一个元素所以全局下限一定是数组里的最大值 max。从 max 开始二分能少搜索不少范围而且避免了一些无谓的检查。3.3 手推一遍二分过程还是用样例 [5, 10, 4]m 2。初始 lo max 10hi sum 19。mid (10 19) / 2 14。检查 limit14 能否成立贪心分块后得到 {5} 和 {10,4}共 2 段不大于 m2可行。于是把上界压缩到 14。mid (10 14) / 2 12。检查{5}、{10}、{4}需要 3 段大于 2不可行。把下界拉到 13。mid (13 14) / 2 13。检查51015 超过 13所以 {5}、{10}、{4}还是 3 段不可行。把下界拉到 14。lo hi 14输出 14。整个流程下来二分大概只会执行 log2(19-10) 次检查大概四五次配上一次 O(n) 的贪心判断总复杂度 O(n log S)S 是数组总和。这个复杂度在机考的时间限制内非常稳。4. 检查函数是灵魂贪心分段的正确写法和证明4.1 一步一步实现检查逻辑检查函数要回答的问题是给定 limit用贪心策略去切分数组能不能保证所需的段数不超过 m。写法是模拟一个累加器 cur从头到尾遍历数组cur 表示当前这个部门已经累积的产出。遇到一个元素 x如果 x 本身大于 limit说明这一段的产出一定超标直接返回不可行如果 cur x 不超过 limit就把 x 放进当前部门累加如果 cur x 超过 limit说明当前部门已经装不下了必须在这里切开新起一个部门段数加一cur 重置为 x。每次段数超过 m就提前返回 false不用遍历完整数。细节上要注意我习惯在新起一段时先判断段数是否超限再给 cur 赋值避免数组只有一个元素但 cur 被错误累加的问题。另外 cur 和 limit 都要用长整型防止求和过程溢出。4.2 为什么贪心产生的段数一定是最少的这里有个很多人会问的问题每次都贪心地尽量把当前部门塞满会不会导致后续分段不优答案是不会。因为判断条件只看“当前总和会不会超过 limit”而塞得越多留给后面的资源就越少后续被拆开的风险只会更低。也就是说这种贪心得到的段数是所有合法切法中最少的。严格一点说假设存在某个合法切法用了 k 段那么贪心切法得到的段数一定不超过 k。因为贪心每一步都让当前段尽可能长相当于把合法切法中的每一段边界都靠后移动段的个数只会减少不会增多。所以贪心段数小于等于 m就等价于存在一种不超过 m 段的合法分配。具备这种“最优化判断”性质的检查函数才能保证二分的正确性。4.3 一个容易忽略的等价写法有的同学会问如果贪心得到的段数小于 m不是应该报错吗比如 m2贪心只切出 1 段显然不行。但注意答案区间下界是 max当 limit 足够大时确实可能 1 段就能装完。可 m 个部门都必须存在至少得有 m 段。遇到这种情况只需要把 1 段再拆细一点拆成任意多段段的总和不超过 limit 依然成立。所以“贪心段数小于等于 m”是可行的充分条件不需要取等。这也是为什么检查函数最后只返回 cnt m而不是 cnt m。5. Java、Python、JS、C、Go 五套代码逐行解读5.1 统一的核心模板不管用什么语言核心就两块二分边界 检查函数。边界用 lo maxhi sumwhile(lo hi) 循环mid lo (hi - lo) / 2。如果 check(mid) 可行就收缩上界 hi mid如果不可行就抬高下界 lo mid 1。这样写的好处是永远不会死循环因为 mid 是整数且 lo 每次至少加一。5.2 Java 实现import java.util.Scanner; public class Main { private static boolean check(long[] a, int m, long limit) { int cnt 1; long cur 0; for (long x : a) { if (x limit) { return false; } if (cur x limit) { cnt; cur x; if (cnt m) { return false; } } else { cur x; } } return cnt m; } public static void main(String[] args) { Scanner sc new Scanner(System.in); int m sc.nextInt(); int n sc.nextInt(); long[] a new long[n]; long sum 0; long max 0; for (int i 0; i n; i) { a[i] sc.nextLong(); sum a[i]; max Math.max(max, a[i]); } long lo max; long hi sum; while (lo hi) { long mid lo (hi - lo) / 2; if (check(a, m, mid)) { hi mid; } else { lo mid 1; } } System.out.println(lo); sc.close(); } }Java 的坑主要在类型上。Scanner 读 long 没问题但 mid 如果写成 (lo hi) / 2当 lo 和 hi 都接近 1e9 级别时相加可能溢出 int更别说 long 相加还有极端风险。所以统一用 lo (hi - lo) / 2这是最稳的写法。5.3 Python 实现def check(a, m, limit): cnt 1 cur 0 for x in a: if x limit: return False if cur x limit: cnt 1 cur x if cnt m: return False else: cur x return cnt m def solve(): m int(input()) n int(input()) a list(map(int, input().split())) lo, hi max(a), sum(a) while lo hi: mid (lo hi) // 2 if check(a, m, mid): hi mid else: lo mid 1 print(lo) if __name__ __main__: solve()Python 的 int 不会溢出写起来最省心。需要注意两点一是 input() 如果遇到空行或前置空格会炸考场判题数据一般规范但本地测试时要小心二是读数组时如果数组跨多行用 sys.stdin.read().split() 一次性读取更稳。import sys def solve(): data list(map(int, sys.stdin.read().split())) m data[0] n data[1] a data[2:] lo, hi max(a), sum(a) while lo hi: mid (lo hi) // 2 if check(a, m, mid): hi mid else: lo mid 1 print(lo)5.4 JavaScript 实现const readline require(readline); function check(a, m, limit) { let cnt 1; let cur 0; for (const x of a) { if (x limit) return false; if (cur x limit) { cnt; cur x; if (cnt m) return false; } else { cur x; } } return cnt m; } const rl readline.createInterface({ input: process.stdin, output: process.stdout }); const lines []; rl.on(line, (line) { lines.push(line.trim()); }); rl.on(close, () { const m parseInt(lines[0]); const n parseInt(lines[1]); const a lines[2].split(/\s/).map(Number); let lo Math.max(...a); let hi a.reduce((acc, x) acc x, 0); while (lo hi) { const mid Math.floor((lo hi) / 2); if (check(a, m, mid)) { hi mid; } else { lo mid 1; } } console.log(lo); });JS 的坑在浮点数上。虽然数值范围只是 int 级别但 Math.floor((lo hi) / 2) 必须显式取整不然可能出现小数 mid导致 check 永远无法收敛。另外 Math.max(...a) 在数组特别大的时候可能爆栈建议改成 for 循环求 max。5.5 C 实现#include bits/stdc.h using namespace std; bool check(const vectorlong long a, int m, long long limit) { int cnt 1; long long cur 0; for (long long x : a) { if (x limit) { return false; } if (cur x limit) { cnt; cur x; if (cnt m) { return false; } } else { cur x; } } return cnt m; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int m, n; cin m n; vectorlong long a(n); long long sum 0; long long maxVal 0; for (int i 0; i n; i) { cin a[i]; sum a[i]; maxVal max(maxVal, a[i]); } long long lo maxVal; long long hi sum; while (lo hi) { long long mid lo (hi - lo) / 2; if (check(a, m, mid)) { hi mid; } else { lo mid 1; } } cout lo \n; return 0; }C 需要注意的是 ios::sync_with_stdio(false) 和 cin.tie(nullptr) 这两行不加的话大数据输入会非常慢。所有累加值用 long long虽然题目说 ai 到 1e9n 到 1e5那 sum 最高 1e14期间计算 cur x 也在这个量级long long 完全扛得住。5.6 Go 实现package main import ( bufio fmt os ) func check(a []int64, m int, limit int64) bool { cnt : 1 var cur int64 for _, x : range a { if x limit { return false } if curx limit { cnt cur x if cnt m { return false } } else { cur x } } return cnt m } func main() { in : bufio.NewReader(os.Stdin) var m, n int fmt.Fscan(in, m, n) a : make([]int64, n) var sum, maxVal int64 for i : 0; i n; i { fmt.Fscan(in, a[i]) sum a[i] if a[i] maxVal { maxVal a[i] } } lo, hi : maxVal, sum for lo hi { mid : lo (hi-lo)/2 if check(a, m, mid) { hi mid } else { lo mid 1 } } fmt.Println(lo) }Go 的 fmt.Fscan 在空格和换行混在一起时也能正确处理这点比较省心。但注意它不会自动跳过大量空行如果判题系统给的输入有多个空白行建议用 bufio.Scanner 按行读再统一解析。整体逻辑和其他语言完全一致只是语法层面的改写。6. 实测踩过的坑边界用例、二分死循环、考场时间分配6.1 三组必须测的用例场景输入期望输出原因部门数大于人数m5, n3, a[7,2,9]9每个人一个部门答案就是最大值只有一个部门m1, n4, a[3,1,4,2]10全部人放一起答案是总和全体相等m3, n4, a[2,2,2,2]3{2,2},{2},{2} 最大段是 4不对最优是 {2},{2},{2,2} 最大是 4等等我重新算最后一行我重新算一下。数组 [2,2,2,2]m3切成 3 段连续的{2}, {2}, {2,2} → 最大 4{2}, {2,2}, {2} → 最大 4{2,2}, {2}, {2} → 最大 4所以答案是 4不是 3。表格里这个示例正好提醒你平均值 8/3 取整 3 只是下界不代表可行贪心检查会给出真实答案。这种用例最容易让手工推演出错建议考场上用代码验证而不是心算。6.2 二分死循环和边界收缩的调试经验我最开始写二分时用的是while (lo hi)配合if (check(mid)) hi mid - 1这种写法当时脑子里的模板和现在的习惯混在一起结果在只有两个数的小区间里疯狂死循环。后来我统一成while (lo hi)配合左闭右开收缩可行就把 hi 拉到 mid不可行就把 lo 抬到 mid1最终答案就是 lo 和 hi 相遇的位置。这套写法我觉得是最不容易出错的。还有一个细节mid (lo hi) / 2在 Java 的 long 加法和 C 的 long long 加法里都可能溢出但mid lo (hi - lo) / 2不会。Python 和 JS 没有这个问题但保持同一种写法可以让你少记一套规则。6.3 考场上的时间分配建议华为OD机考一般至少有两道代码题通常一道简单一道中等偏难有的场次还会有第三道。“部门人力分配”属于中等偏上的二分答案题如果前面四十分钟还没完整跑通我会先把它放在后面做。不是因为它解不出来而是这类二分题调试起来很耗时一旦检查函数有小 bug很容易陷入反复试探的泥潭。我习惯的流程是先把所有题都看一遍做掉最有把握的再回头啃二分。做这题时先写检查函数再写二分主循环最后补主函数读入和输出每一步都用一个简单用例自测一次。这样即便时间不够至少保证已经拿下了简单题的分。最后再分享一个我个人的小技巧检查函数里的越界判断if x limit虽然是保险代码但在考场上能帮你避免一类非常隐晦的错误。哪怕二分下界已经保证 limit 不小于最大值这行代码也只多几行留着不吃亏。所有语言实现我都保留了它就是希望在关键时刻给你兜个底。