华为OD机试真题—— 流水线（2025B卷：100分）Java/python/JavaScript/C/C++/GO最佳实现

2025 B卷 100分 题型

本专栏内全部题目均提供Java、python、JavaScript、C、C++、GO六种语言的最佳实现方式；

并且每种语言均涵盖详细的问题分析、解题思路、代码实现、代码详解、3个测试用例以及综合分析；

本文收录于专栏：《2025华为OD真题目录+全流程解析+备考攻略+经验分享》

华为OD机试真题《流水线》：

---

文章快捷目录

题目描述及说明

Java

python

JavaScript

C++

C

GO

---

题目名称：流水线

---

知识点：排序、贪心算法（最小堆）
时间限制：1秒
空间限制：256MB
限定语言：不限

---

题目描述

一个工厂有 m 条流水线，用于并行完成 n 个独立作业。调度系统在安排作业时，优先执行处理时间最短的作业。
当 n > m 时，处理时间最短的 m 个作业先进入流水线，其余作业等待。当某流水线作业完成后，从剩余作业中选择最短的补入。
要求计算处理完所有作业的总耗时。

---

输入描述

• 第一行为两个整数（空格分隔），表示流水线个数 m 和作业数 n。
• 第二行为 n 个整数（空格分隔），表示每个作业的处理时长 t1, t2, ..., tn。
• 取值范围：0 < m, n < 100，0 < t1, t2...tn < 100。

---

输出描述

输出处理完所有作业的总时长。

---

示例

输入

3 5  
8 4 3 2 10  

输出

13  

说明

1. 初始分配最短的 3 个作业 2,3,4 进入流水线。
2. 流水线1完成时间 2，补入剩余最短作业 8。
3. 流水线2完成时间 3，补入剩余作业 10。
4. 最终最长耗时为 3 + 10 = 13。

---

Java

问题分析

我们需要调度多个作业到流水线，使得总耗时最短。每个流水线同一时间只能处理一个作业，且优先分配给处理时间最短的作业。总耗时由所有流水线中耗时最长的决定。

解题思路

1. 排序作业：先将所有作业按处理时间从小到大排序。
2. 贪心分配：使用最小堆模拟流水线，每次选择当前总时间最小的流水线，分配下一个最短作业。
3. 计算总耗时：最后所有流水线的总时间中的最大值即为答案。

代码实现

import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int m = scanner.nextInt(); // 流水线数量int n = scanner.nextInt(); // 作业数量int[] tasks = new int[n]; // 存储每个作业的处理时间for (int i = 0; i < n; i++) {tasks[i] = scanner.nextInt();}Arrays.sort(tasks); // 按处理时间升序排列PriorityQueue<Integer> pq = new PriorityQueue<>(); // 最小堆，存储各流水线当前总时间int initialJobs = Math.min(m, n); // 初始分配的作业数（不超过流水线数）for (int i = 0; i < initialJobs; i++) {pq.add(tasks[i]); // 初始作业分配给流水线}// 处理剩余的作业（当n > m时）for (int i = m; i < n; i++) {int earliestEnd = pq.poll(); // 取出当前最早空闲的流水线earliestEnd += tasks[i]; // 分配新作业到该流水线pq.add(earliestEnd); // 将新总时间重新加入堆}// 找到堆中的最大总时间，即为总耗时int maxTime = 0;while (!pq.isEmpty()) {maxTime = Math.max(maxTime, pq.poll());}System.out.println(maxTime);}
}

代码解析

1. 输入处理：读取流水线数 m、作业数 n 及每个作业的处理时间存入数组。
2. 排序作业：将作业按处理时间从小到大排序，确保优先分配最短作业。
3. 初始化堆：将前 m 个（或全部作业如果少于 m）作业直接加入最小堆，表示初始分配的流水线时间。
4. 处理剩余作业：对于后续作业，每次从堆中取出当前总时间最小的流水线，加上新作业时间后重新插入堆，动态调整流水线负载。
5. 计算总耗时：遍历堆中的总时间，取最大值即为所有作业完成的总耗时。

示例测试

示例输入1：

3 5  
8 4 3 2 10  

输出1：13
解析：初始分配 2、3、4 → 流水线时间 [2,3,4]。剩余作业 8 → 2+8=10，队列变为 [3,4,10]。作业 10 → 3+10=13，队列变为 [4,10,13]。最大时间为13。

示例输入2：

2 4  
1 2 3 4  

输出2：6
解析：初始分配 1、2 → 流水线时间 [1,2]。剩余作业 3 → 1+3=4，队列 [2,4]。作业4 → 2+4=6。最大时间6。

示例输入3：

5 3  
5 3 1  

输出3：5
解析：初始分配 1、3、5 → 最大时间5（无需处理后续作业）。

综合分析

• 时间复杂度：O(n log n) 来自排序，O(n log m) 来自堆操作，总体 O(n log n)。
• 空间复杂度：O(m) 用于存储堆，m ≤ 100，空间高效。
• 贪心选择正确性：每次选择最短作业分配到最早空闲流水线，确保总耗时最小。
• 适用性：适用于作业调度、资源分配等场景，高效处理大规模数据。

---

python

问题分析

本问题要求将多个作业调度到流水线，使得所有作业完成的总时间最短。流水线按处理时间最短优先分配作业，总耗时由最长完成时间的流水线决定。

---

解题思路

1. 排序作业：将作业按处理时间从小到大排序，确保优先分配最短作业。
2. 贪心调度：使用最小堆维护当前流水线的完成时间，每次选取最早空闲的流水线分配新的最短作业。
3. 计算总耗时：最终所有流水线的完成时间中的最大值即为答案。

---

代码实现

import heapqdef main():# 读取输入m, n = map(int, input().split())tasks = list(