【AtCoder版！蟻本】CODE THANKS FESTIVAL 2017 C - Factory【priority-queue】 - ebisukeプログラミング初心者脱出黙示録

f:id:ebisuke33:20210801003043p:plain

AtCoder版！蟻本のpriority-queueの例題としてあげられているABC012 D - バスと避けられない運命をPythonで解いていきます。

リンク

問題文

工場にプレゼントを作る機械が N 台あります。i ( 1 ≦ i ≦ N ) 番目の機械は、最初 ai 秒でプレゼントを 1 個作れます。
しかし、ある機械でプレゼントを 1 個作るたびにその機械のみが劣化して、プレゼントを 1 個作るのにかかる時間が bi 秒増えます。
したがって、i ( 1 ≦ i ≦ N ) 番目の機械で si 個目のプレゼントを作るのに　ai+( si − 1 )×bi 秒かかります。
また、工場に供給される電力が少ないため、複数の機械を同時に動かすことはできません。

イルカはプレゼント K 個をできる限り短い時間で製造したいです。
プレゼントの製造にかかる最小の合計時間を求めてください。

制約

・1 ≦ N ≦ 10^5
・1 ≦ K ≦ 10^5
・1 ≦ ai ≦ 10^9
・0 ≦ bi ≦ 10^9
・入力は全て整数である。

解答例

import heapq

n, k = map(int,input().split())

A = []
B = []
for i in range(n):
    a, b = map(int,input().split())
    heapq.heappush(A, (a, i))
    B.append(b)

ans = 0
for i in range(k):
    tmp, j = heapq.heappop(A)
    ans += tmp
    heapq.heappush(A, (tmp + B[j], j))

print(ans)