SamCoding Round 11 (Div. 1) B - GPU Queue
- サイト
- SamCoding
- コンテスト
- SamCoding Round 11 (Div. 1)
- 問題
- B - GPU Queue(常設版)
台の GPU と、実行時間が順に であるタスクがあります。各 GPU は同時に 個のタスクを処理でき、空いた GPU が待ち行列の先頭のタスクをすぐに実行します。
時刻 から処理を始めたとき、すべてのタスクが完了する時刻を求める問題です()。
各 GPU が次に空く時刻を管理し、タスクを先頭から順に割り当てます。
あるタスクを実行できるのは、最も早く空く GPU です。その時刻を 、タスクの実行時間を とすると、その GPU が次に空く時刻は になります。同時に空く GPU が複数あっても、どれに割り当てるかで空く時刻の集合は変わりません。
最も早く空く時刻を効率よく取り出すため、最小ヒープを使います。最初はすべての GPU が空いているので、 を 個入れます。各タスクについて、最小値 を取り出し、 をヒープに戻します。
すべてのタスクを割り当てた後、各 GPU に割り当てた最後のタスクの完了時刻がヒープに残ります。その最大値が、すべてのタスクの完了時刻です。GPU がタスクより多い場合に残る も、そのままで構いません。
計算量は 、ヒープに必要な空間は です。
Python
import heapq
N, M = map(int, input().split())T = list(map(int, input().split()))
hq = [0] * Mfor t in T: x = heapq.heappop(hq) heapq.heappush(hq, x + t)print(max(hq))