コンテンツにスキップ

SamCoding Round 11 (Div. 1) B - GPU Queue

サイト
SamCoding
コンテスト
SamCoding Round 11 (Div. 1)
問題
B - GPU Queue(常設版)

MM 台の GPU と、実行時間が順に T1,T2,…,TNT_1,T_2,\dots,T_N であるタスクがあります。各 GPU は同時に 11 個のタスクを処理でき、空いた GPU が待ち行列の先頭のタスクをすぐに実行します。

時刻 00 から処理を始めたとき、すべてのタスクが完了する時刻を求める問題です(N,M≤2×105N,M \le 2\times10^5)。

各 GPU が次に空く時刻を管理し、タスクを先頭から順に割り当てます。

あるタスクを実行できるのは、最も早く空く GPU です。その時刻を xx、タスクの実行時間を tt とすると、その GPU が次に空く時刻は x+tx+t になります。同時に空く GPU が複数あっても、どれに割り当てるかで空く時刻の集合は変わりません。

最も早く空く時刻を効率よく取り出すため、最小ヒープを使います。最初はすべての GPU が空いているので、00 を MM 個入れます。各タスクについて、最小値 xx を取り出し、x+tx+t をヒープに戻します。

すべてのタスクを割り当てた後、各 GPU に割り当てた最後のタスクの完了時刻がヒープに残ります。その最大値が、すべてのタスクの完了時刻です。GPU がタスクより多い場合に残る 00 も、そのままで構いません。

計算量は O(M+Nlog⁡(M+1))O(M+N\log(M+1))、ヒープに必要な空間は O(M)O(M) です。

Python
import heapq
N, M = map(int, input().split())
T = list(map(int, input().split()))
hq = [0] * M
for t in T:
x = heapq.heappop(hq)
heapq.heappush(hq, x + t)
print(max(hq))