题目描述
一个工厂有 m 条流水线，来并行完成 n 个独立的作业。该工厂设置了一个调度系统，在安排作业时，总是优先执行处理时间最短的作业。
现给定流水线个数 m，需要完成的作业数 n，每个作业的处理时间分别为 t_1, t_2, \dots, t_n。请你编程计算处理完所有作业的耗时为多少？
调度规则：
当 n > m 时，首先处理时间短的 m 个作业进入流水线，其他的等待。当某个作业完成时（即某条流水线空闲），依次从剩余作业中取处理时间最短的进入处理。
输入描述
- 第一行为 2 个整数（采用空格分隔），分别表示流水线个数 m 和作业数 n。
- 第二行输入 n 个整数（采用空格分隔），表示每个作业的处理时长 t_1, t_2, \dots, t_n。
- 约束：0 < m, n < 100，0 < t_i < 100。
- 注：保证输入都是合法的。
输出描述
- 输出处理完所有作业的总时长。
示例 1
输入
3 5
8 4 3 2 10
输出
13
说明
- 排序：首先将作业按处理时间升序排序：
2, 3, 4, 8, 10。 - 初始分配：有 3 条流水线，先安排时间最短的 3 个作业（2, 3, 4）分别进入 3 条流水线。
- 流水线 1：耗时 2
- 流水线 2：耗时 3
- 流水线 3：耗时 4
- 后续调度：
- 时刻 2：流水线 1 最先完成（耗时 2）。剩余作业中最短的是 8。流水线 1 接手作业 8，流水线 1 总耗时变为 2 + 8 = 10。
- 时刻 3：流水线 2 接下来完成（耗时 3）。剩余作业中最短的是 10。流水线 2 接手作业 10，流水线 2 总耗时变为 3 + 10 = 13。
- 时刻 4：流水线 3 完成（耗时 4）。此时所有作业已分配完毕，流水线 3 空闲。
- 最终结果：所有作业处理完的时间取决于最慢的那条流水线。
- 流水线 1 完成时刻：10
- 流水线 2 完成时刻：13
- 流水线 3 完成时刻：4
- 最大值为 13。
💡 解题思路与代码优化
原始代码分析
原始代码尝试使用 i % m 来分配任务，这在任务已经排序且按照轮询方式分配时是可行的，但逻辑上不如直接寻找“最早空闲的流水线”直观和稳健。
此外，原始代码在 n <= m 时直接打印结果后没有 return，会导致后续代码继续执行，可能引发数组越界异常。
优化方案
- 贪心策略：题目要求“总是优先执行处理时间最短的作业”，因此第一步必须对作业时间数组进行升序排序。
- 模拟调度：
- 我们需要维护 m 条流水线当前的完成时刻。
- 对于剩余的每一个作业（从第 m+1 个开始），我们应该将其分配给当前完成时刻最早（即数值最小）的那条流水线。
- 分配后，更新该流水线的完成时刻（原完成时刻 + 新作业时长）。
- 数据结构：可以使用一个数组或列表来存储每条流水线的当前完成时间。每次分配时，遍历该数组找到最小值及其索引。
- 结果：所有作业分配完毕后，数组中的最大值即为总耗时。
优化后的 Java 代码
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
/**
* 题目：流水线调度
* 优化思路：贪心算法 + 模拟
*/
public class AssembleLineOptimized {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取第一行 m 和 n
if (!scanner.hasNextLine()) return;
String[] mnLine = scanner.nextLine().trim().split(" ");
int m = Integer.parseInt(mnLine);
int n = Integer.parseInt(mnLine);[[source_group_web_1]]
// 读取第二行作业时间
if (!scanner.hasNextLine()) return;
String[] timeLine = scanner.nextLine().trim().split(" ");
int[] times = new int[n];
for (int i = 0; i < n; i++) {
times[i] = Integer.parseInt(timeLine[i]);
}
// 1. 贪心策略：作业时间升序排序
Arrays.sort(times);
// 2. 边界情况：如果作业数 <= 流水线数
// 所有作业可以同时开始，总耗时就是最长的那个作业时间
if (n <= m) {
System.out.println(times[n - 1]);
return; // 重要：直接返回，避免后续逻辑错误
}
// 3. 模拟流水线
// lines[i] 表示第 i 条流水线当前的完成时刻
List<Integer> lines = new ArrayList<>();
// 初始化：前 m 个作业分别分配给 m 条流水线
for (int i = 0; i < m; i++) {
lines.add(times[i]);
}
// 处理剩余的作业 (从第 m 个索引开始，即第 m+1 个作业)
for (int i = m; i < n; i++) {
int jobTime = times[i];
// 找到当前完成时刻最早的流水线（最小值）
int minTime = Collections.min(lines);
int minIndex = lines.indexOf(minTime);
// 将该作业分配给这条流水线
// 新的完成时刻 = 当前完成时刻 + 新作业耗时
lines.set(minIndex, minTime + jobTime);
}
// 4. 结果是所有流水线完成时刻的最大值
int maxTime = Collections.max(lines);
System.out.println(maxTime);
}
}