多机调度问题

题目描述

某工厂有 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
5 2
8 6 5 5 4

14

数据范围

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