大模型训练 - 华为机试真题第二题（200分）

考试平台： 时习知

题目类型： 3 道编程题 （100分 + 200分 + 300分）

考试时间： 2024-01-24 （两小时）

AI大模型学习大量的训练样本，通过大量参数拟合出样本背后复杂的高维概率密度分布关系。由于训练数据量越来越大，参数越来越多，模型越来越大，传统超级计算机算力和资源有限无法满足训练需求，假设可通过量了计算机来进行人模型训练。

现有简化后训练了任务模型列表 tasks， tasks[i] 表示第 i个子任务模型的算力需求，为了保证模型计算的SLA要求所有的子任务模型在T个时刻内完成计算。

每个时刻，需按照给出子任务模型的算力需求列表( tasks )顺序调度到量了计算机并完成计算。

任意时刻调度的多个了任务模型的算力需求总和不会超过量了计算机可承载的最人算力负荷请返回量了计算机需要提供的最低算力，可在T个时刻内计算完全部子任务模型

输入

输入包括两行，第一行包含2个整数N，T，分别表示子任务模型列表长度，计算全部了任务模型的时刻要求

第二行包含N个整数: tasks[1] tasks[2] tasks[3] … tasks[n] 分别表示第 i个子任务模型的算力需求

注意:

(1) 1 <= T <= N <= 50000

(2) 1 <= tasks[i] <= 500

输出

输出一行，包含一个整数，表示量子计算机需要提供的最低算力，可在T个时刻内计算完全部子任务模型

示例1

输入：
10 5
1 2 3 4 5 6 7 8 9 10输出：
15解释：
量子计算机需要提供的最低算力15，能够满足5个时刻内计算全部子任务模型的需要:时刻1: 1,2.3,4,5;时刻2: 6,7: 时刻3: 8: 时刻4: 9: 时刻5: 10

示例2

输入：
6 3
4 4 2 1 2 3输出：
6解释：
量子计算机需要提供的最低算力6，能够满足3个时刻内计算全部子任务模型的需要:时刻1: 4;时刻2: 4,2，时刻3: 1,2,3

示例3

输入：
5 4
1 3 2 1 1输出：
3解释：
量子计算机需要提供的最低算力3，能够满足4个时刻内计算全部子任务模型的需要:时刻1: 1,时刻2:3,时刻3: 2,1,时刻4: 1

题解

这道题目属于二分查找的问题。题目要求找到一个最小的算力值，使得在指定的时刻内能够完成所有子任务模型的计算。具体的解题思路如下：

1. 确定二分查找的上下界：上界 r 可以设为所有任务算力的总和，下界 l 可以设为最大的任务算力值减去1。
2. 在每一次二分查找的过程中，计算中间值 m，表示当前的计算机算力。
3. 编写一个辅助函数 ok，用于判断在当前计算机算力下，是否能够在指定时刻内完成所有子任务模型的计算。该函数返回一个布尔值，表示能否完成。
4. 如果 ok 函数返回 True，说明当前算力值够大，可以在指定时刻内完成计算，将上界 r 缩小为 m；否则，将下界 l 增大为 m。
5. 重复步骤 2 到步骤 4，直到找到最小的算力值。

这种类型的二分查找问题在实际应用中比较常见，需要通过不断调整上下界来找到满足特定条件的最小值。

def ok(tasks, m, t) -> bool:""" 计算机算力为 m, tasks 中的任务能否在 t 个时刻内完成 """cost, remain = 0, 0  # 已经花费的时刻数， 剩余的计算机算力for task in tasks:if remain < task:  # 剩余算力不足，需要新建计算机，并且花费 1 个时刻数remain = m - taskcost += 1else:remain -= taskreturn cost <= tdef func():n, t = map(int, input().split())tasks = list(map(int, input().split()))l, r = max(tasks) - 1, sum(tasks)while l + 1 < r:m = (l + r) // 2if ok(tasks, m, t):r = melse:l = mprint(r)if __name__ == "__main__":func()

🙏整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏