一、题目题目描述一个工厂有 m 条流水线来并行完成 n 个独立的作业该工厂设置了一个调度系统在安排作业时总是优先执行处理时间最短的作业。现给定流水线个数 m需要完成的作业数 n每个作业的处理时间分别为 t1, t2 ... tn。请你编程计算处理完所有作业的耗时为多少当 n m 时首先处理时间短的 m 个作业进入流水线其他的等待当某个作业完成时依次从剩余作业中取处理时间最短的进入处理。输入描述第一行为 2 个整数采用空格分隔分别表示流水线个数 m 和作业数 n第二行输入 n 个整数采用空格分隔表示每个作业的处理时长 t1, t2 ... tn。0 m, n 1000 t1, t2 ... tn 100注保证输入都是合法的。输出描述输出处理完所有作业的总时长示例输入3 58 4 3 2 10输出13说明先安排时间为 2、3、4 的 3 个作业。第一条流水线先完成作业时间 2然后调度剩余时间最短的作业 8。第二条流水线完成作业时间 3然后调度剩余时间最短的作业 10。总工时就是第二条流水线完成作业的时间 133 10。这道题是贪心算法与数据结构优先队列的经典结合。1. 为什么用贪心题目明确规定了策略“总是优先执行处理时间最短的作业”。直觉如果先做长任务长任务会长时间占用流水线导致后续短任务排队等待增加整体完工时间。操作第一步必须对所有作业时长数组进行升序排序。2. 为什么用最小堆Min-Heap这是本题的难点。我们需要实时知道哪条流水线最早空闲状态维护我们需要维护 mm 个数字代表 mm 条流水线当前的预计完工时刻。动态决策每当有新任务来时必须找到这 mm 个数字中的最小值最早空闲的线将其更新为最小值 新任务时长。效率对比暴力遍历每次找最小值需 O(m)O(m) 总复杂度 O(n×m)O(n×m) 。最小堆获取最小值 O(1)O(1) 插入/调整 O(logm)O(logm) 总复杂度 O(nlogm)O(nlogm) 。结论使用最小堆是标准且最优的解法。3. 算法步骤图解排序将任务数组tasks从小到大排序。特判若 n≤mn≤m 所有任务可并行直接返回最大任务时长。建堆取前 mm 个任务时长放入最小堆代表初始完工时间。模拟遍历剩余任务pop()堆顶最早完工时间t_min。计算新时间t_new t_min current_task。push(t_new)回堆。结果遍历堆中所有元素取最大值即为答案。三、Python 实现Python 的heapq模块原生支持最小堆代码极其简洁是机考中的“版本答案”。import sys import heapq def solve(): # 【输入处理】 # 使用 sys.stdin.read().split() 可以一次性读取所有输入并自动按空白符分割 # 完美应对换行、多空格等不规范的输入格式 input_data sys.stdin.read().split() if not input_data: return iterator iter(input_data) try: m int(next(iterator)) n int(next(iterator)) tasks [] for _ in range(n): tasks.append(int(next(iterator))) except StopIteration: return # 【步骤1贪心排序】 tasks.sort() # 【步骤2边界处理】 # 如果任务数 流水线数所有任务同时开始耗时取决于最长的那个 if n m: print(tasks[-1] if tasks else 0) return # 【步骤3初始化最小堆】 # 将前 m 个任务的时长放入堆中 # heapq.heapify 可以在 O(m) 时间内将列表转化为堆 pq tasks[:m] heapq.heapify(pq) # 【步骤4模拟调度】 # 遍历剩余的 n-m 个任务 for i in range(m, n): task_time tasks[i] # 弹出堆顶当前最早完工的流水线时刻 earliest_finish heapq.heappop(pq) # 该流水线接上新任务更新完工时刻 new_finish earliest_finish task_time # 将新时刻推回堆中堆会自动调整保持最小值在堆顶 heapq.heappush(pq, new_finish) # 【步骤5获取结果】 # 此时堆中存储了所有流水线的最终完工时刻 # 题目要求的是总耗时即所有流水线中最晚结束的时间最大值 # 注意堆顶是最小值不能直接取堆顶需要遍历整个堆 max_time max(pq) print(max_time) if __name__ __main__: solve() Python 代码亮点输入鲁棒性sys.stdin.read().split()是处理机考输入的万能钥匙无需关心换行符位置。高效建堆heapq.heapify()比循环heappush更快。逻辑清晰核心模拟循环仅 4 行代码完美体现 Python 的简洁美。四、JavaScript 实现手写最小堆由于 JavaScript 原生标准库在大多数机考环境如 Node.js 旧版本或浏览器中没有内置优先队列我们需要手写一个最小堆类。这是前端/全栈考生必须掌握的基本功。const readline require(readline); // // 最小堆类实现 (MinHeap) // class MinHeap { constructor() { this.heap []; } // 获取父节点索引 getParentIndex(i) { return Math.floor((i - 1) / 2); } // 获取左子节点索引 getLeftIndex(i) { return 2 * i 1; } // 获取右子节点索引 getRightIndex(i) { return 2 * i 2; } // 交换元素 swap(i, j) { [this.heap[i], this.heap[j]] [this.heap[j], this.heap[i]]; } // 向上调整 (插入新元素时调用) shiftUp(index) { if (index 0) return; const parentIndex this.getParentIndex(index); // 如果当前节点比父节点小则交换 if (this.heap[index] this.heap[parentIndex]) { this.swap(index, parentIndex); this.shiftUp(parentIndex); } } // 向下调整 (删除堆顶后调用) shiftDown(index) { const leftIndex this.getLeftIndex(index); const rightIndex this.getRightIndex(index); let smallest index; // 寻找当前节点及其子节点中的最小值 if (leftIndex this.heap.length this.heap[leftIndex] this.heap[smallest]) { smallest leftIndex; } if (rightIndex this.heap.length this.heap[rightIndex] this.heap[smallest]) { smallest rightIndex; } // 如果最小值不是当前节点则交换并继续向下调整 if (smallest ! index) { this.swap(index, smallest); this.shiftDown(smallest); } } // 插入元素 push(value) { this.heap.push(value); this.shiftUp(this.heap.length - 1); } // 弹出堆顶元素 (最小值) pop() { if (this.heap.length 0) return null; if (this.heap.length 1) return this.heap.pop(); const top this.heap[0]; // 将最后一个元素移到堆顶 this.heap[0] this.heap.pop(); // 向下调整 this.shiftDown(0); return top; } // 获取堆数组用于最后找最大值 toArray() { return this.heap; } size() { return this.heap.length; } } // // 主逻辑 // function solve() { const rl readline.createInterface({ input: process.stdin, output: process.stdout }); const lines []; rl.on(line, (line) { lines.push(line.trim()); }); rl.on(close, () { // 【输入处理】 // 将所有行合并按空白符分割过滤空字符串 const allTokens lines.join( ).split(/\s/).filter(t t ! ); if (allTokens.length 2) return; const m parseInt(allTokens[0]); const n parseInt(allTokens[1]); const tasks []; for (let i 0; i n; i) { tasks.push(parseInt(allTokens[2 i])); } // 【步骤1贪心排序】 tasks.sort((a, b) a - b); // 【步骤2边界处理】 if (n m) { console.log(n 0 ? 0 : tasks[n - 1]); return; } // 【步骤3初始化堆】 const pq new MinHeap(); for (let i 0; i m; i) { pq.push(tasks[i]); } // 【步骤4模拟调度】 for (let i m; i n; i) { // 弹出最早完工时间 const earliestFinish pq.pop(); // 加上新任务时间 const newFinish earliestFinish tasks[i]; // 推回堆 pq.push(newFinish); } // 【步骤5获取结果】 // 遍历堆中所有元素找最大值 const finalTimes pq.toArray(); const maxTime Math.max(...finalTimes); console.log(maxTime); }); } solve(); JavaScript 代码亮点完整封装MinHeap类实现了标准的堆操作shiftUp,shiftDown可直接复用到其他算法题中。输入兼容通过readline收集所有行再统一解析避免了因输入换行导致的解析错误。逻辑严谨严格遵循“弹出最小 - 累加 - 推入”的贪心模拟流程。五、避坑指南⚠️结果取值陷阱❌错误做法输出最后一次计算的结果或者直接输出pq.pop()。✅正确做法堆顶永远是最小值最早完工时间而题目求的是总耗时最晚完工时间。必须在循环结束后遍历堆内所有元素取Math.max或max()。边界条件 n≤mn≤m当任务数少于等于流水线数时不需要进堆模拟。直接输出排序后数组的最后一个元素最大任务时长即可。忽略此判断可能导致代码逻辑冗余甚至报错。输入格式机考系统的输入有时会在同一行有时分多行。Python 的split()和 JS 的join( ).split(/\s/)是最稳健的处理方式。六、总结本题是考察贪心思想与优先队列应用的经典题目。Python 选手利用heapq库3分钟即可写出 AC 代码。JS 选手手写MinHeap类虽然代码量稍大但能充分展示对数据结构的理解是加分项。掌握“排序 最小堆模拟”这一模板你就能轻松解决各类资源调度、任务分配问题。祝大家在机考中旗开得胜
【华为OD机考真题】流水线调度 · 最短完工时间 (Python /JS)
一、题目题目描述一个工厂有 m 条流水线来并行完成 n 个独立的作业该工厂设置了一个调度系统在安排作业时总是优先执行处理时间最短的作业。现给定流水线个数 m需要完成的作业数 n每个作业的处理时间分别为 t1, t2 ... tn。请你编程计算处理完所有作业的耗时为多少当 n m 时首先处理时间短的 m 个作业进入流水线其他的等待当某个作业完成时依次从剩余作业中取处理时间最短的进入处理。输入描述第一行为 2 个整数采用空格分隔分别表示流水线个数 m 和作业数 n第二行输入 n 个整数采用空格分隔表示每个作业的处理时长 t1, t2 ... tn。0 m, n 1000 t1, t2 ... tn 100注保证输入都是合法的。输出描述输出处理完所有作业的总时长示例输入3 58 4 3 2 10输出13说明先安排时间为 2、3、4 的 3 个作业。第一条流水线先完成作业时间 2然后调度剩余时间最短的作业 8。第二条流水线完成作业时间 3然后调度剩余时间最短的作业 10。总工时就是第二条流水线完成作业的时间 133 10。这道题是贪心算法与数据结构优先队列的经典结合。1. 为什么用贪心题目明确规定了策略“总是优先执行处理时间最短的作业”。直觉如果先做长任务长任务会长时间占用流水线导致后续短任务排队等待增加整体完工时间。操作第一步必须对所有作业时长数组进行升序排序。2. 为什么用最小堆Min-Heap这是本题的难点。我们需要实时知道哪条流水线最早空闲状态维护我们需要维护 mm 个数字代表 mm 条流水线当前的预计完工时刻。动态决策每当有新任务来时必须找到这 mm 个数字中的最小值最早空闲的线将其更新为最小值 新任务时长。效率对比暴力遍历每次找最小值需 O(m)O(m) 总复杂度 O(n×m)O(n×m) 。最小堆获取最小值 O(1)O(1) 插入/调整 O(logm)O(logm) 总复杂度 O(nlogm)O(nlogm) 。结论使用最小堆是标准且最优的解法。3. 算法步骤图解排序将任务数组tasks从小到大排序。特判若 n≤mn≤m 所有任务可并行直接返回最大任务时长。建堆取前 mm 个任务时长放入最小堆代表初始完工时间。模拟遍历剩余任务pop()堆顶最早完工时间t_min。计算新时间t_new t_min current_task。push(t_new)回堆。结果遍历堆中所有元素取最大值即为答案。三、Python 实现Python 的heapq模块原生支持最小堆代码极其简洁是机考中的“版本答案”。import sys import heapq def solve(): # 【输入处理】 # 使用 sys.stdin.read().split() 可以一次性读取所有输入并自动按空白符分割 # 完美应对换行、多空格等不规范的输入格式 input_data sys.stdin.read().split() if not input_data: return iterator iter(input_data) try: m int(next(iterator)) n int(next(iterator)) tasks [] for _ in range(n): tasks.append(int(next(iterator))) except StopIteration: return # 【步骤1贪心排序】 tasks.sort() # 【步骤2边界处理】 # 如果任务数 流水线数所有任务同时开始耗时取决于最长的那个 if n m: print(tasks[-1] if tasks else 0) return # 【步骤3初始化最小堆】 # 将前 m 个任务的时长放入堆中 # heapq.heapify 可以在 O(m) 时间内将列表转化为堆 pq tasks[:m] heapq.heapify(pq) # 【步骤4模拟调度】 # 遍历剩余的 n-m 个任务 for i in range(m, n): task_time tasks[i] # 弹出堆顶当前最早完工的流水线时刻 earliest_finish heapq.heappop(pq) # 该流水线接上新任务更新完工时刻 new_finish earliest_finish task_time # 将新时刻推回堆中堆会自动调整保持最小值在堆顶 heapq.heappush(pq, new_finish) # 【步骤5获取结果】 # 此时堆中存储了所有流水线的最终完工时刻 # 题目要求的是总耗时即所有流水线中最晚结束的时间最大值 # 注意堆顶是最小值不能直接取堆顶需要遍历整个堆 max_time max(pq) print(max_time) if __name__ __main__: solve() Python 代码亮点输入鲁棒性sys.stdin.read().split()是处理机考输入的万能钥匙无需关心换行符位置。高效建堆heapq.heapify()比循环heappush更快。逻辑清晰核心模拟循环仅 4 行代码完美体现 Python 的简洁美。四、JavaScript 实现手写最小堆由于 JavaScript 原生标准库在大多数机考环境如 Node.js 旧版本或浏览器中没有内置优先队列我们需要手写一个最小堆类。这是前端/全栈考生必须掌握的基本功。const readline require(readline); // // 最小堆类实现 (MinHeap) // class MinHeap { constructor() { this.heap []; } // 获取父节点索引 getParentIndex(i) { return Math.floor((i - 1) / 2); } // 获取左子节点索引 getLeftIndex(i) { return 2 * i 1; } // 获取右子节点索引 getRightIndex(i) { return 2 * i 2; } // 交换元素 swap(i, j) { [this.heap[i], this.heap[j]] [this.heap[j], this.heap[i]]; } // 向上调整 (插入新元素时调用) shiftUp(index) { if (index 0) return; const parentIndex this.getParentIndex(index); // 如果当前节点比父节点小则交换 if (this.heap[index] this.heap[parentIndex]) { this.swap(index, parentIndex); this.shiftUp(parentIndex); } } // 向下调整 (删除堆顶后调用) shiftDown(index) { const leftIndex this.getLeftIndex(index); const rightIndex this.getRightIndex(index); let smallest index; // 寻找当前节点及其子节点中的最小值 if (leftIndex this.heap.length this.heap[leftIndex] this.heap[smallest]) { smallest leftIndex; } if (rightIndex this.heap.length this.heap[rightIndex] this.heap[smallest]) { smallest rightIndex; } // 如果最小值不是当前节点则交换并继续向下调整 if (smallest ! index) { this.swap(index, smallest); this.shiftDown(smallest); } } // 插入元素 push(value) { this.heap.push(value); this.shiftUp(this.heap.length - 1); } // 弹出堆顶元素 (最小值) pop() { if (this.heap.length 0) return null; if (this.heap.length 1) return this.heap.pop(); const top this.heap[0]; // 将最后一个元素移到堆顶 this.heap[0] this.heap.pop(); // 向下调整 this.shiftDown(0); return top; } // 获取堆数组用于最后找最大值 toArray() { return this.heap; } size() { return this.heap.length; } } // // 主逻辑 // function solve() { const rl readline.createInterface({ input: process.stdin, output: process.stdout }); const lines []; rl.on(line, (line) { lines.push(line.trim()); }); rl.on(close, () { // 【输入处理】 // 将所有行合并按空白符分割过滤空字符串 const allTokens lines.join( ).split(/\s/).filter(t t ! ); if (allTokens.length 2) return; const m parseInt(allTokens[0]); const n parseInt(allTokens[1]); const tasks []; for (let i 0; i n; i) { tasks.push(parseInt(allTokens[2 i])); } // 【步骤1贪心排序】 tasks.sort((a, b) a - b); // 【步骤2边界处理】 if (n m) { console.log(n 0 ? 0 : tasks[n - 1]); return; } // 【步骤3初始化堆】 const pq new MinHeap(); for (let i 0; i m; i) { pq.push(tasks[i]); } // 【步骤4模拟调度】 for (let i m; i n; i) { // 弹出最早完工时间 const earliestFinish pq.pop(); // 加上新任务时间 const newFinish earliestFinish tasks[i]; // 推回堆 pq.push(newFinish); } // 【步骤5获取结果】 // 遍历堆中所有元素找最大值 const finalTimes pq.toArray(); const maxTime Math.max(...finalTimes); console.log(maxTime); }); } solve(); JavaScript 代码亮点完整封装MinHeap类实现了标准的堆操作shiftUp,shiftDown可直接复用到其他算法题中。输入兼容通过readline收集所有行再统一解析避免了因输入换行导致的解析错误。逻辑严谨严格遵循“弹出最小 - 累加 - 推入”的贪心模拟流程。五、避坑指南⚠️结果取值陷阱❌错误做法输出最后一次计算的结果或者直接输出pq.pop()。✅正确做法堆顶永远是最小值最早完工时间而题目求的是总耗时最晚完工时间。必须在循环结束后遍历堆内所有元素取Math.max或max()。边界条件 n≤mn≤m当任务数少于等于流水线数时不需要进堆模拟。直接输出排序后数组的最后一个元素最大任务时长即可。忽略此判断可能导致代码逻辑冗余甚至报错。输入格式机考系统的输入有时会在同一行有时分多行。Python 的split()和 JS 的join( ).split(/\s/)是最稳健的处理方式。六、总结本题是考察贪心思想与优先队列应用的经典题目。Python 选手利用heapq库3分钟即可写出 AC 代码。JS 选手手写MinHeap类虽然代码量稍大但能充分展示对数据结构的理解是加分项。掌握“排序 最小堆模拟”这一模板你就能轻松解决各类资源调度、任务分配问题。祝大家在机考中旗开得胜
