解题思路

算法选择：LPT 贪心 + 最小堆

1. 将样本时长按从大到小排序。
2. 使用一个大小为 n 的最小堆（优先队列）来维护每个 NPU 的当前负载，初值全为 0。
3. 依次取出当前最大的样本，把它放到当前负载最小的 NPU 上（堆顶），更新该 NPU 的负载并压回堆。
4. 全部分配完成后，所有 NPU 负载中的最大值即为答案。

直觉：把大的任务优先安排，并始终让它落到当前最“空闲”的设备，可有效压低最大负载。

题目内容

大模型训练通常采用数据并行的训练方式，处理大规模数据集(样本)，加速训练过程，具休的:

假设有$n$个$NPU$，$m$个样本，把$m$个样本分给$n$个$NPU$，每个$NPU$上有一份完整模型，各自计算自己的样本数据，其中$m>=n$，保证每个$NPU$至少分到一个样本，且样本不能切分，一个样本必须完整的被分到个$NPU$上

每个$NPU$的运行时间跟所分到的样本的长度和呈正相关。如果每个$NPU$上的样本长度和相差较大，会形成木桶效应，执行快的$NPU$等待执行慢的$NPU$，最终执行时间由最大样本和长度的$NPU$决定。

试着编号一段程序对样本进行均衡分配，设$n$个$NPU$上分得的最大的样本和为$l_{max}$，使$l_{max}$最小，即求$min(l_{max})$

输入描述

第一行为$1$个整数$n(0< n< 1000)$，表示$NPU$的个数

第二行为$1$个整数$m(0 < m< 10000)$，表示样本的个数

第三行有$m$个处于区间$[1,100000]$之内的整数，表示$m$个样本中每个样本的长度

输出描述

输出$1$个整数(行尾没有空格)，该数字表示$min(l_{max})$的值,

样例1

输入

4
7
89 245 64 128 79 166 144

输出

245

说明

样本根据$NPU$个数进行分组，一共有$4$个$NPU$，所以有$4$个分组，最优样本分配如下:

$(1)79,144 \ (2)245 \ (3)64，166 \ (4)128，89$

求和分别为:$223，245，230，217$；$4$个$NPU$中最大的样本长度和为$245$、所以输出$245$

样例2

输入

2
3
145 274 100

输出

274

样本根据$NPU$个数进行分组，一共有$2$个$NPU$，$3$个样本；所以有$2$个分出，有以下$3$种分法:

$(1)145,274+100；(2)274,145+100；(3)100，145+274$

$3$种分法的最大样本和分别为:$374，274，419$;

所以第$2$种分法超均衡，最大样本和长度最小，为$274$，所以输出274