【ABC141 D】「Powerful Discount Tickets」を解く【Python3】

コンテスト一覧へ

 

N個の品物をM枚の割引券を用いて購入するときに、すべての品物を買える最小の金額がいくらなのか、を計算する問題です。

提出
import heapq

n, m = map(int, input().split())
a = list(map(lambda x: int(x) * (-1), input().split()))

heapq.heapify(a)

for i in range(m):
    num = heapq.heappop(a)
    heapq.heappush(a, -(-num//2))

print(-sum(a))

値段の高い品物に割引券を利用した方が、最終金額を安くできます。

M枚の割引券を1枚ずつ使用する方法で考えると上手くいきます。

値段のリストから最大値を取り出し、(1/2)倍してリストに戻すというのを繰り返します。

(一枚ずつ使用しても、一度に使用しても、割引券の数が等しければ、同じく「X/2Y(切り捨て)」になります)

(1/2)倍した後に、リスト内にこれよりも高い品物がある場合、割引券を無駄にしてしまうので、そのつど最大値を取り出すようにします。

実際には、heapq.heapify()でリストを優先度付きキューに変換して、最小値を取り出しています。

事前にリストの要素をマイナスにしておき、最小値を取り出して、(1/2)倍の切り上げを行い、リストに戻します。

割引券の枚数分繰り返し、最終的にリストの合計値を正の整数に戻したものが答えになります。

スポンサーリンク

【ABC141】解説記事リスト

コンテスト一覧に戻る

コメントを残す

メールアドレスが公開されることはありません。