华为OD机考的双机位C卷这两年题库迭代很快算法题的风格也从“背模板就能过”转向了“题目场景包装 多语言工程实现”的混合体。“部门人力分配”就是典型代表它表面上是一个开发排期调度题实际上考的是二分答案的单调性判断外加一个高效的可行性验证函数。这篇文章我会把这个题从读题到AC完整走一遍用 Java、Python、JavaScript、C/C、Go 五套语言给出可运行的代码并把容易踩的坑一次性说清楚。无论你是刚开始刷华为OD机试还是已经上手了A/B卷想看看C卷的套路这篇都能给你一个可以直接抄作业的参考。1. 题目到底在考什么先读懂“部门人力分配”1.1 还原题目场景和输入输出我在机考时拿到的“部门人力分配”场景大致是这样的某个部门手上有 n 个开发任务每个任务要连续占用一个人力若干天领导给定一个工期上限 T问至少配置多少名开发人员才能保证所有任务在 T 天内收尾。输入通常是两行第一行一个整数 T代表工期上限天第二行 n 个整数是每个任务的耗时。输出是一个整数表示最少需要的人力数。举例来说如果 T 5任务耗时为 4、3、3、2、2、1那么 3 个人是能排开的第一个人干 4 和 1第二个人干 3 和 2第三个人干 3 和 2每个人的累计工时都是 5刚好踩线2 个人则无论如何都放不下因为总工时 15 已经超过了 2 × 510。所以答案就是 3。有些题库会把输入顺序换成“先任务数组后 T”也有变体会反过来问“给定 K 个人求最短工期”。核心思路完全一致都是二分一个整数然后写一个判定函数。1.2 为什么不能靠排序或除法直接出答案很多人第一反应是把任务从大到小排序然后按“总工时 ÷ T”向上取整或者平均分配给每个人。这里有个很典型的反例T 8任务耗时是 7、7、7、1。总工时 22ceil(22 / 8) 3但你实际用 3 个人试试每个人最多干 8 天只能安排下“71”和“7”第三个 7 天任务没人接得住必须上第 4 个人。这个例子说明“总工时 ÷ T”只是理论下界。任务之间不能拆分放桶里会有碎片时间而碎片时间没法跨人合并所以真实答案往往大于这个下界。这本质上是一个装箱问题变种不能用一个简单的数学公式一步到位。那为什么能二分因为“k 个人能不能在 T 天内完成”这个判断在 k 增大的时候是单调的人越多方案一定不会比人少的时候更差。这种单调性把“求最优分配”转化成“反复判断某个 k 是否可行”于是二分答案就成了最自然的主框架。1.3 单调性的直觉证明假设 k 个人能完成往里再加一个人有两种处理方式要么让新来的人闲着原有 k 人的排期完全不变照样能在 T 天内完成要么从某个已经很忙的人身上拆一个任务给新人剩余的人负载只会更轻。无论哪种k1 个人都一定可行。反过来如果 k 个人不可行那 k-1 个人更不可能因为每个人身上已经有更多任务了。所以可行性函数是一个前段全是 false、后段全是 true 的阶梯状曲线二分查找这个“false 变 true”的分界点就是我们要求的最少人数。2. 解题框架二分答案 可行性验证2.1 二分边界和下界优化直接二分人力数 k范围取 1 到 n 就已经安全。任务一共有 n 个最极端情况下每个任务单独给一个人所以 n 一定是一个可行解可以作为上界。下界可以做一点优化减少二分次数总工时 sum每人最多工作 T 天所以至少需要 ceil(sum / T) 个人最长的单个任务 maxTask如果它都大于 T说明无解题目一般会保证这类数据不出现两个条件取最大值就是更紧的左边界。例如 T 5、任务 [4,3,3,2,2,1] 时sum 15ceil(15 / 5) 3maxTask 4所以左边界可以直接从 3 开始查不用从 1 慢慢试。二分模板我习惯写成左闭右开最后 left 就是答案int left Math.max(1, (sum T - 1) / T); int right n; while (left right) { int mid left (right - left) / 2; if (canFinish(mid)) { right mid; } else { left mid 1; } }2.2 check 函数的两条路线回溯精确版与堆贪心提速版先说清楚一个关键点把 n 个任务放进 k 个桶每个桶容量 T这本身是 NP 难的装箱问题变种。所以机考里真正拉开差距的不是二分框架而是 check 函数怎么写。路线一DFS 回溯精确判断。把任务按耗时从大到小排序依次尝试放进每一个桶如果某个任务所有桶都放不下立刻返回 false。桶的数量就是 k配合剪枝任务数 n 在 20 左右时完全跑得动。这个方案的结果是精确的只要存在可行排法DFS 一定能找到。路线二小顶堆贪心。每次拿当前耗时最大的任务分配给“当前累计工时最少”的人。如果这个人加上这个任务就超过 T说明不可行。这个方案排序 O(n log n)、分配 O(n log k)适合 n 很大的场景但它是近似算法理论上存在误判可能。我自己的机考策略是先用 sum 和 maxTask 做一个快速下界判断如果 n 比较小直接用 DFS 回溯n 大到 10^3 以上就改堆贪心来赌测试数据。两种 check 都放在文章里大家按数据范围选择。2.3 DFS 剪枝的三个关键点回溯版本的 check 虽然精确但不剪枝就是指数爆炸。我实测下来这三个剪枝最有用第一从大到小排序。大任务先放小任务用来填空隙这样能尽早触发“放不下”的分支剪掉整棵子树如果先放小任务桶里到处都是碎片大任务放不进去时已经晚了。第二桶负载去重。两个桶当前累计工时相同比如都是 3那么把当前任务放进这两个桶后续搜索空间是完全对称的只需要试第一个另一个直接跳过。用 Set 或者按桶下标判断都能实现。第三提前判 maxTask T。如果单个任务本身就超工期无论多少人都不可能完成check 直接返回 false不用进二分。3. 五套语言完整实现与逐段拆解3.1 Java 实现Java 在华为OD机考里是使用率最高的语言之一代码写起来中规中矩重点是把 Scanner 读取和二分模板写稳。import java.util.*; public class Main { static int limit; static int[] tasks; static int n; public static void main(String[] args) { Scanner sc new Scanner(System.in); limit sc.nextInt(); ListInteger list new ArrayList(); while (sc.hasNextInt()) { list.add(sc.nextInt()); } n list.size(); tasks new int[n]; long sum 0; int maxTask 0; for (int i 0; i n; i) { tasks[i] list.get(i); sum tasks[i]; maxTask Math.max(maxTask, tasks[i]); } if (maxTask limit) { System.out.println(-1); return; } // 从大到小排序DFS 剪枝更有效 Arrays.sort(tasks); for (int i 0, j n - 1; i j; i, j--) { int tmp tasks[i]; tasks[i] tasks[j]; tasks[j] tmp; } int left (int) Math.max(1, (sum limit - 1) / limit); int right n; while (left right) { int mid left (right - left) / 2; if (canFinish(mid)) { right mid; } else { left mid 1; } } System.out.println(left); } static boolean canFinish(int k) { int[] buckets new int[k]; return dfs(buckets, 0); } static boolean dfs(int[] buckets, int idx) { if (idx n) return true; int t tasks[idx]; SetInteger tried new HashSet(); for (int i 0; i buckets.length; i) { if (tried.contains(buckets[i])) continue; if (buckets[i] t limit) continue; tried.add(buckets[i]); buckets[i] t; if (dfs(buckets, idx 1)) return true; buckets[i] - t; } return false; } }这段代码里我用了 Set 做桶负载去重。很多新手会忽略这个剪枝结果一旦任务数超过 15DFS 就跑不动了。加上之后同样规模的数据运行时间能差出几十倍。3.2 Python 实现与递归深度坑Python 写回溯最舒服但有一个隐藏问题默认递归深度只有 1000。如果任务数逼近 1000递归层数一深就直接 RecursionError。所以代码里我加了一行sys.setrecursionlimit。import sys from typing import List sys.setrecursionlimit(1000000) def can_finish(tasks: List[int], limit: int, k: int) - bool: buckets [0] * k n len(tasks) def dfs(idx: int) - bool: if idx n: return True t tasks[idx] tried set() for i in range(k): load buckets[i] if load in tried: continue if load t limit: continue tried.add(load) buckets[i] load t if dfs(idx 1): return True buckets[i] load return False tasks.sort(reverseTrue) return dfs(0) def min_workers(limit: int, tasks: List[int]) - int: if not tasks: return 0 total sum(tasks) max_task max(tasks) if max_task limit: return -1 left max(1, (total limit - 1) // limit) right len(tasks) while left right: mid (left right) // 2 if can_finish(tasks, limit, mid): right mid else: left mid 1 return left if __name__ __main__: limit int(sys.stdin.readline()) tasks list(map(int, sys.stdin.readline().split())) print(min_workers(limit, tasks))注意这里我在回溯里做了“先记录原负载再还原”的操作而不是写buckets[i] - t。因为 t 是局部变量直接记录原负载更不容易出错尤其是同一个任务的负载可能被 Set 跳过时。3.3 JavaScript / Node.js 实现JS 在牛客网和大部分OD机考平台上是按 Node.js 跑的输入输出走标准流。读取两行后直接按行处理即可。const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout, }); const lines []; rl.on(line, (line) { lines.push(line.trim()); if (lines.length 2) { const limit parseInt(lines[0], 10); const tasks lines[1].split(/\s/).map(Number); console.log(minWorkers(limit, tasks)); rl.close(); } }); function minWorkers(limit, tasks) { if (!tasks.length) return 0; const total tasks.reduce((a, b) a b, 0); const maxTask Math.max(...tasks); if (maxTask limit) return -1; tasks.sort((a, b) b - a); let left Math.max(1, Math.ceil(total / limit)); let right tasks.length; while (left right) { const mid left Math.floor((right - left) / 2); if (canFinish(tasks, limit, mid)) { right mid; } else { left mid 1; } } return left; } function canFinish(tasks, limit, k) { const buckets new Array(k).fill(0); const n tasks.length; function dfs(idx) { if (idx n) return true; const t tasks[idx]; const tried new Set(); for (let i 0; i k; i) { const load buckets[i]; if (tried.has(load)) continue; if (load t limit) continue; tried.add(load); buckets[i] load t; if (dfs(idx 1)) return true; buckets[i] load; } return false; } return dfs(0); }JS 的Set对数字的哈希处理很快但在极端情况下频繁创建 Set 也有开销。如果 n 很小其实可以直接用一个普通数组标记已经尝试过的负载速度会更快。3.4 C/C 实现C 版本最适合用来分析复杂度因为所有操作都摊在明面上。我直接用vectorint存任务和桶配合unordered_set去重。#include bits/stdc.h using namespace std; int limit; int n; vectorint tasks; bool dfs(vectorint buckets, int idx) { if (idx n) return true; int t tasks[idx]; unordered_setint tried; for (int i 0; i (int)buckets.size(); i) { int load buckets[i]; if (tried.count(load)) continue; if (load t limit) continue; tried.insert(load); buckets[i] load t; if (dfs(buckets, idx 1)) return true; buckets[i] load; } return false; } bool canFinish(int k) { vectorint buckets(k, 0); return dfs(buckets, 0); } int main() { cin limit; int x; long long sum 0; int maxTask 0; while (cin x) { tasks.push_back(x); sum x; maxTask max(maxTask, x); } n tasks.size(); if (maxTask limit) { cout -1 endl; return 0; } sort(tasks.rbegin(), tasks.rend()); int left max(1LL, (sum limit - 1) / limit); int right n; while (left right) { int mid left (right - left) / 2; if (canFinish(mid)) { right mid; } else { left mid 1; } } cout left endl; return 0; }如果你在牛客网这类平台上提交注意头文件用bits/stdc.h可能在某些编译器上不被接受保险起见可以拆分成iostream、vector、algorithm、unordered_set。另外输入的cin x会一直读到 EOF适合单组用例如果题目有多组用例需要自己控制循环条件。3.5 Go 实现Go 写算法题的体验挺特别切片就是引用类型递归时要注意桶数组千万别在函数间意外共享。好在我们直接用同一个切片做回溯每次还原负载即可。package main import ( bufio fmt os sort strconv strings ) var ( limit int tasks []int n int ) func dfs(buckets []int, idx int) bool { if idx n { return true } t : tasks[idx] tried : make(map[int]bool) for i : 0; i len(buckets); i { load : buckets[i] if tried[load] { continue } if loadt limit { continue } tried[load] true buckets[i] load t if dfs(buckets, idx1) { return true } buckets[i] load } return false } func canFinish(k int) bool { buckets : make([]int, k) return dfs(buckets, 0) } func main() { scanner : bufio.NewScanner(os.Stdin) scanner.Scan() limit, _ strconv.Atoi(scanner.Text()) scanner.Scan() parts : strings.Fields(scanner.Text()) var sum int64 maxTask : 0 for _, p : range parts { v, _ : strconv.Atoi(p) tasks append(tasks, v) sum int64(v) if v maxTask { maxTask v } } n len(tasks) if maxTask limit { fmt.Println(-1) return } sort.Sort(sort.Reverse(sort.IntSlice(tasks))) left : int(max(int64(1), (sumint64(limit)-1)/int64(limit))) right : n for left right { mid : left (right-left)/2 if canFinish(mid) { right mid } else { left mid 1 } } fmt.Println(left) } func max(a, b int64) int64 { if a b { return a } return b }Go 里面没有内置的 int64 max所以我自己加了一个。这种“手写基础函数”的细节在机考里特别容易被忽略但恰恰是 Go 考试里最实在的得分点。4. 常见问题与双机位实战经验4.1 排序方向写反导致回溯指数爆炸我见过不少同学把任务从小到大排序然后丢进回溯里。结果大任务全放在最后才处理前面小任务把桶都占满了等大任务来了才发现所有桶都放不下回溯要反复重试无数层直接超时。一定要记住先排大任务大任务先入桶才能让“放不下”的分支尽早出现剪枝效率才高。4.2 Python 递归深度和 JS 输入读取Python 版必须设置sys.setrecursionlimit并且最好把递归深度限制提高到任务数的两倍以上。JS 版最坑的是readline的事件回调是异步的如果你在line事件里直接执行逻辑要确保lines.length 2时再开始计算否则第二行还没读完就跑了数组会缺数据。4.3 边界输入和 sum 的类型任务数量和单任务耗时如果很大sum 可能超过 int 范围。Java 里我用 long 累加C 里也用了 long longGo 里用了 int64。二分时的 mid 计算我统一写了left (right - left) / 2避免 left right 溢出。这些看起来是小事但在机考环境里一旦踩到排查起来非常浪费时间。另外还有一个容易被忽略的边界如果任务数组为空直接返回 0如果存在单个任务耗时大于 T直接返回无解标记。很多人的二分代码会在这种输入下输出一个错误的 n导致一个用例都过不了。4.4 双机位考试的环境准备既然是“双机位C卷”考试时有两个摄像头正面机位拍人脸侧面或后置机位拍桌面和屏幕。这意味着你不能低头看手机、不能翻纸质笔记桌面上尽量只放证件、电脑、鼠标键盘。考试平台一般要求提前 30 分钟进入调试摄像头和麦克风浏览器权限要允许调用摄像头。代码这块我的建议是提前在本机配好 Java、Python、Node.js、C 编译器、Go 环境但机考通常是在线 OJ最终以在线编译结果为准平时练习时不要依赖 IDE 自动补全尤其是 Java 的import和 C 的头文件要能随手敲出来输入输出必须严格按题目来多用Scanner和readline的标准输入模式练习别在代码里写死文件路径。在C卷里多语言版本的换着写并不难真正难的是快速识别题型。看到“最少人数”“最短时间”“能否在限制内完成”这类字眼第一反应就应该是二分答案而不是一股脑去写贪心或 DP。最后两个小经验送给准备上机的人第一个经验如果这道题你在二分里把 check 写成了回溯但 n 太大一直超时别急着优化回溯先回去看能不能换堆贪心。我之前就在一道类似题上卡了四十分钟后来把 check 改成小顶堆贪心一秒就跑了。第二个经验输入读取时如果题目说第二行可能有多个数字但不确定长度就用while (cin x)或scanner.hasNextInt()来读不要用for (int i 0; i n; i)去读因为你可能根本不知道 n 到底是多少。这个习惯我在 Java 和 C 里都踩过坑现在写题凡是读取一行数组默认都是读到流结束。部门人力分配这个题难度不算顶但它把二分答案和可行性验证这两个高频考点串在了一起。把这道题吃透像“项目排期”“最短工期”“运输装载”这一挂的题思路就都能打通了。希望你上机时能一次AC。