P3561.第2题-大模型训练数据均衡分配算法

1000ms

Difficulty: 5

所属公司 : 华为

算法与标签>贪心算法

题目内容

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

假设有 $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})$ 的值,

输入

4
7
89 245 64 128 79 166 144

输出

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

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

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

输入

2
3
145 274 100

输出

样本根据 $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

输入

预期输出（选填）