一、题目

题目描述：
一个工厂有 m 条流水线，来并行完成 n 个独立的作业，该工厂设置了一个调度系统，在安排作业时，总是优先执行处理时间最短的作业。
现给定流水线个数 m，需要完成的作业数 n，每个作业的处理时间分别为 t1, t2 ... tn。请你编程计算处理完所有作业的耗时为多少？
当 n > m 时，首先处理时间短的 m 个作业进入流水线，其他的等待，当某个作业完成时，依次从剩余作业中取处理时间最短的进入处理。
输入描述：
第一行为 2 个整数（采用空格分隔），分别表示流水线个数 m 和作业数 n
第二行输入 n 个整数（采用空格分隔），表示每个作业的处理时长 t1, t2 ... tn。
0 < m, n < 100
0 < t1, t2 ... tn < 100
注：保证输入都是合法的。
输出描述：
输出处理完所有作业的总时长

示例

输入：
3 5
8 4 3 2 10

输出：
13

说明：
先安排时间为 2、3、4 的 3 个作业。
第一条流水线先完成作业（时间 2），然后调度剩余时间最短的作业 8。
第二条流水线完成作业（时间 3），然后调度剩余时间最短的作业 10。
总工时就是第二条流水线完成作业的时间 13（3 + 10）。

二、解题思路：贪心 + 最小堆模拟

1. 核心逻辑

这道题是一个典型的贪心算法结合优先队列的问题。

• 贪心策略：为了让总时间最短，必须让忙碌的流水线尽早空闲下来去接新的活。因此，总是把新任务交给当前预计完成时间最早的那条流水线。同时，任务本身也要按从小到大的顺序处理，确保短任务优先被消化。
• 数据结构：我们需要一个数据结构来维护 mm 条流水线的当前完成时间，并能快速取出最小值。这正是最小堆（Min-Heap）的用武之地。

2. 算法步骤

1. 排序：将 n 个作业时长数组 tasks 从小到大排序。
2. 初始化堆：
   • 如果 n≤m ：直接返回最大的那个作业时长（因为可以并行同时做）。
   • 如果 n>m ：将前 m 个作业的时长放入最小堆中，代表 m 条流水线目前的完工时间。
3. 模拟调度：
   • 遍历剩余的 n−m 个作业。
   • 每次从堆顶弹出最小值 min_time（代表最早空闲的流水线时刻）。
   • 将该时刻加上当前作业时长 task，得到新的完工时间 new_time = min_time + task。
   • 将 new_time 重新推入堆中。
4. 获取结果：
   • 当所有作业都分配完毕后，堆中存储的是每条流水线的最终完工时间。
   • 答案即为堆中的最大值。
   • 技巧：在 Go/Java 中，堆弹空后的最后一个元素，或者遍历堆数组找最大值即可。其实更简单的逻辑是：最后一次弹出的 min_time 加上对应的 task 并不一定是最大值，必须遍历堆中所有元素取最大值，或者在循环结束后，不断弹出堆直到只剩一个最大值（不推荐，破坏结构），最直接的方法是遍历堆底层数组找最大。

3. 复杂度分析

• 时间复杂度：
  • 排序： O(Nlog⁡N) 。
  • 堆操作：共进行 N−m 次入堆和出堆，每次 O(log⁡M) 。
  • 总复杂度： O(Nlog⁡N+Nlog⁡M) 。鉴于 N,M<100 ，效率极高。
• 空间复杂度： O(M) 用于存储堆。

---

三、代码实现💻

1. Java 实现

Java 拥有强大的标准库 java.util.PriorityQueue，默认就是最小堆，实现非常简洁。

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取 m 和 n
        if (!scanner.hasNextInt()) return;
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        
        int[] tasks = new int[n];
        for (int i = 0; i < n; i++) {
            tasks[i] = scanner.nextInt();
        }
        
        // 1. 贪心：先对作业时长排序
        Arrays.sort(tasks);
        
        // 特殊情况：如果作业数少于等于流水线数，耗时就是最长的那个作业
        if (n <= m) {
            System.out.println(tasks[n - 1]);
            return;
        }
        
        // 2. 初始化最小堆，存储每条流水线的“当前完成时间”
        // Java PriorityQueue 默认是最小堆
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        // 先将前 m 个作业分配给 m 条流水线
        for (int i = 0; i < m; i++) {
            pq.offer(tasks[i]);
        }
        
        // 3. 模拟调度过程
        for (int i = m; i < n; i++) {
            // 取出最早完成的流水线时间
            int earliestFinishTime = pq.poll();
            
            // 将当前最短作业分配给它，计算新的完成时间
            int newFinishTime = earliestFinishTime + tasks[i];
            
            // 放回堆中
            pq.offer(newFinishTime);
        }
        
        // 4. 结果是所有流水线完成时间的最大值
        // 此时堆中可能有多个元素，需要遍历找最大值
        int maxTime = 0;
        for (int time : pq) {
            if (time > maxTime) {
                maxTime = time;
            }
        }
        
        System.out.println(maxTime);
        scanner.close();
    }
}

2. Go 实现

Go 的标准库 container/heap 需要用户实现 heap.Interface 接口。虽然稍微繁琐一点，但能让我们更深入理解堆的底层运作，且性能极佳。

package main

import (
	"container/heap"
	"fmt"
	"sort"
)

// IntHeap 定义一个最小堆类型
type IntHeap []int

// 实现 heap.Interface 接口的五个方法

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] } // 最小堆：小的在上面
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func solve() {
	var m, n int
	if _, err := fmt.Scan(&m, &n); err != nil {
		return
	}

	tasks := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&tasks[i])
	}

	// 1. 贪心：排序
	sort.Ints(tasks)

	// 特殊情况
	if n <= m {
		fmt.Println(tasks[n-1])
		return
	}

	// 2. 初始化堆
	h := &IntHeap{}
	heap.Init(h)

	// 放入前 m 个作业
	for i := 0; i < m; i++ {
		heap.Push(h, tasks[i])
	}

	// 3. 模拟调度
	for i := m; i < n; i++ {
		// 弹出最小值（最早完成的流水线时间）
		earliest := heap.Pop(h).(int)
		
		// 加上新作业时间
		newTime := earliest + tasks[i]
		
		// 推回堆
		heap.Push(h, newTime)
	}

	// 4. 找最大值
	maxTime := 0
	for _, t := range *h {
		if t > maxTime {
			maxTime = t
		}
	}

	fmt.Println(maxTime)
}

func main() {
	solve()
}

---

四、关键点深度解析🔍

1. 为什么必须先排序作业？

题目明确要求“总是优先执行处理时间最短的作业”。

• 如果不排序，直接按输入顺序分配，可能会导致长作业阻塞了流水线，而短作业在后面等待，违背了题目的调度规则。
• 排序保证了我们每次取出的 tasks[i] 都是当前剩余任务中最小的，符合贪心策略。

2. 为什么用最小堆维护流水线时间？

• 我们的目标是找到“谁最先闲着”。
• 数组遍历找最小值是 O(M) ，而堆顶取值是 O(1) ，调整堆是 O(log⁡M) 。
• 在 N 较大时，堆的优势非常明显。本题虽然 N,M<100 数据量小，但在机考中养成使用合适数据结构的习惯至关重要。

3. 结果为何是堆中的最大值？

• 堆中存储的是每条流水线最终的任务完成时刻。
• 整个工厂完工，取决于最慢的那条流水线。
• 注意：堆顶是最小值（最早完成的），所以不能直接 Pop 出来当结果，必须遍历堆内所有元素取 Max。

4. 边界情况处理

• n≤m ：作业比流水线少或刚好够分。此时所有作业同时开始，总耗时就是单个作业中最长的那个（排序后的最后一个）。代码中做了特判，避免逻辑复杂化。
• 输入合法性：题目保证合法，实际工程中可增加对 m=0 等的防御性编程。

---

五、总结与建议🚀

这道题是“多机调度问题”的一个简化变种（带有特定贪心规则）。

• 思维转换：将物理世界的“流水线空闲”抽象为数字世界中的“最小值弹出”。
• 语言特性：
  • Java：利用 PriorityQueue 可以快速写出生产级代码，适合追求开发效率的场景。
  • Go：通过实现 heap.Interface，展示了 Go 接口组合的灵活性，适合对性能和底层控制有要求的场景。

给考生的建议：

1. 熟记模板：Java 的 PriorityQueue 用法和 Go 的 heap 接口实现模板要烂熟于心。
2. 审题细节：注意题目中的“优先执行短作业”是指任务队列的排序，而“空闲即插”是指资源的分配策略，两者结合才是正解。
3. 结果提取：千万不要以为堆顶就是答案，对于“完工时间”类问题，答案往往是集合中的最大值。

掌握这种“排序 + 优先队列模拟”的模式，你可以轻松解决类似的资源分配、任务调度、甚至哈夫曼编码构造等问题！