多机调度问题

题目描述

某工厂有 n 个独立的作业，由 m 台相同的机器进行加工处理。作业 i 所需的加工时间为 ti，任何作业在被处理时不能中断，也不能进行拆分处理。请计算将 n 个作业分配给 m 台机器加工的最短完成时间（即所有机器中最长的加工时间）。

输入格式

• 第一行输入整数 T（1 < T < 100），表示测试数据组数。
• 每组测试数据格式：
  • 第一行：两个整数 n 和 m（1 ≤ n ≤ 10000，1 ≤ m ≤ 100），分别表示作业数和机器数。
  • 第二行：n 个整数 ti（1 ≤ ti ≤ 100），表示每个作业的加工时间。

输出格式

对于每组测试数据，输出最短完成时间。

样例输入

2
2 2
1 5
7 3
2 14 4 16 6 5 3

样例输出

5
17

提示

1. 若机器数 m ≥ n：每个作业可分配给单独机器，最短时间为最长作业时间。
2. 若机器数 m = 1：所有作业需在一台机器上处理，最短时间为所有作业时间之和。
3. 一般情况：采用“大作业优先分配至当前负载最小机器”的贪心策略，可高效得到最优解。

数据范围

• 测试组数 T：2 ≤ T ≤ 99
• 作业数 n：1 ≤ n ≤ 10000
• 机器数 m：1 ≤ m ≤ 100
• 作业时间 ti：1 ≤ ti ≤ 100