考試平臺(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ì)算。具體的解題思路如下：

1. 確定二分查找的上下界：上界 r 可以設(shè)為所有任務(wù)算力的總和，下界 l 可以設(shè)為最大的任務(wù)算力值減去1。
2. 在每一次二分查找的過程中，計(jì)算中間值 m，表示當(dāng)前的計(jì)算機(jī)算力。
3. 編寫一個(gè)輔助函數(shù) ok，用于判斷在當(dāng)前計(jì)算機(jī)算力下，是否能夠在指定時(shí)刻內(nèi)完成所有子任務(wù)模型的計(jì)算。該函數(shù)返回一個(gè)布爾值，表示能否完成。
4. 如果 ok 函數(shù)返回 True，說明當(dāng)前算力值夠大，可以在指定時(shí)刻內(nèi)完成計(jì)算，將上界 r 縮小為 m；否則，將下界 l 增大為 m。
5. 重復(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è)贊 ???? 和收藏 ?，讓更多的人看到。🙏🙏🙏