網(wǎng)站制作 牛商網(wǎng)外鏈查詢工具
考試平臺(tái): 時(shí)習(xí)知
題目類型: 3 道編程題 (100分 + 200分 + 300分)
考試時(shí)間: 2024-01-24 (兩小時(shí))
AI大模型學(xué)習(xí)大量的訓(xùn)練樣本,通過大量參數(shù)擬合出樣本背后復(fù)雜的高維概率密度分布關(guān)系。由于訓(xùn)練數(shù)據(jù)量越來越大,參數(shù)越來越多,模型越來越大,傳統(tǒng)超級(jí)計(jì)算機(jī)算力和資源有限無法滿足訓(xùn)練需求,假設(shè)可通過量了計(jì)算機(jī)來進(jìn)行人模型訓(xùn)練。
現(xiàn)有簡化后訓(xùn)練了任務(wù)模型列表 tasks, tasks[i] 表示第 i個(gè)子任務(wù)模型的算力需求,為了保證模型計(jì)算的SLA要求所有的子任務(wù)模型在T個(gè)時(shí)刻內(nèi)完成計(jì)算。
每個(gè)時(shí)刻,需按照給出子任務(wù)模型的算力需求列表( tasks )順序調(diào)度到量了計(jì)算機(jī)并完成計(jì)算。
任意時(shí)刻調(diào)度的多個(gè)了任務(wù)模型的算力需求總和不會(huì)超過量了計(jì)算機(jī)可承載的最人算力負(fù)荷請(qǐng)返回量了計(jì)算機(jī)需要提供的最低算力,可在T個(gè)時(shí)刻內(nèi)計(jì)算完全部子任務(wù)模型
輸入
輸入包括兩行,第一行包含2個(gè)整數(shù)N,T,分別表示子任務(wù)模型列表長度,計(jì)算全部了任務(wù)模型的時(shí)刻要求
第二行包含N個(gè)整數(shù): tasks[1] tasks[2] tasks[3] … tasks[n] 分別表示第 i個(gè)子任務(wù)模型的算力需求
注意:
(1) 1 <= T <= N <= 50000
(2) 1 <= tasks[i] <= 500
輸出
輸出一行,包含一個(gè)整數(shù),表示量子計(jì)算機(jī)需要提供的最低算力,可在T個(gè)時(shí)刻內(nèi)計(jì)算完全部子任務(wù)模型
示例1
輸入:
10 5
1 2 3 4 5 6 7 8 9 10輸出:
15解釋:
量子計(jì)算機(jī)需要提供的最低算力15,能夠滿足5個(gè)時(shí)刻內(nèi)計(jì)算全部子任務(wù)模型的需要:時(shí)刻1: 1,2.3,4,5;時(shí)刻2: 6,7: 時(shí)刻3: 8: 時(shí)刻4: 9: 時(shí)刻5: 10
示例2
輸入:
6 3
4 4 2 1 2 3輸出:
6解釋:
量子計(jì)算機(jī)需要提供的最低算力6,能夠滿足3個(gè)時(shí)刻內(nèi)計(jì)算全部子任務(wù)模型的需要:時(shí)刻1: 4;時(shí)刻2: 4,2,時(shí)刻3: 1,2,3
示例3
輸入:
5 4
1 3 2 1 1輸出:
3解釋:
量子計(jì)算機(jī)需要提供的最低算力3,能夠滿足4個(gè)時(shí)刻內(nèi)計(jì)算全部子任務(wù)模型的需要:時(shí)刻1: 1,時(shí)刻2:3,時(shí)刻3: 2,1,時(shí)刻4: 1
題解
這道題目屬于二分查找的問題。題目要求找到一個(gè)最小的算力值,使得在指定的時(shí)刻內(nèi)能夠完成所有子任務(wù)模型的計(jì)算。具體的解題思路如下:
- 確定二分查找的上下界:上界
r
可以設(shè)為所有任務(wù)算力的總和,下界l
可以設(shè)為最大的任務(wù)算力值減去1。- 在每一次二分查找的過程中,計(jì)算中間值
m
,表示當(dāng)前的計(jì)算機(jī)算力。- 編寫一個(gè)輔助函數(shù)
ok
,用于判斷在當(dāng)前計(jì)算機(jī)算力下,是否能夠在指定時(shí)刻內(nèi)完成所有子任務(wù)模型的計(jì)算。該函數(shù)返回一個(gè)布爾值,表示能否完成。- 如果
ok
函數(shù)返回True
,說明當(dāng)前算力值夠大,可以在指定時(shí)刻內(nèi)完成計(jì)算,將上界r
縮小為m
;否則,將下界l
增大為m
。- 重復(fù)步驟 2 到步驟 4,直到找到最小的算力值。
這種類型的二分查找問題在實(shí)際應(yīng)用中比較常見,需要通過不斷調(diào)整上下界來找到滿足特定條件的最小值。
def ok(tasks, m, t) -> bool:""" 計(jì)算機(jī)算力為 m, tasks 中的任務(wù)能否在 t 個(gè)時(shí)刻內(nèi)完成 """cost, remain = 0, 0 # 已經(jīng)花費(fèi)的時(shí)刻數(shù), 剩余的計(jì)算機(jī)算力for task in tasks:if remain < task: # 剩余算力不足,需要新建計(jì)算機(jī),并且花費(fèi) 1 個(gè)時(shí)刻數(shù)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()
🙏整理題解不易, 如果有幫助到您,請(qǐng)給點(diǎn)個(gè)贊 ???? 和收藏 ?,讓更多的人看到。🙏🙏🙏