ABC141 D - Powerful Discount Tickets

問題原文

問題要旨

値段がそれぞれ $a_i$ 円であるような商品が $N$ 個あり、あなたは $M$ 枚の割引券を持っている。
ある商品に割引券を $m$ 枚使うと、その商品を $\frac{a_{i}}{2^{m}}$ （小数点以下切り捨て）円で買うことができる。
割引券を適切に使った場合、全ての商品を買うのにはいくらかかるか。

$1 \leq N \leq 10^{5}$
$1 \leq M \leq 10^{5}$
$1 \leq a_i \leq 10^{9}$

解法

m枚使う → １枚ずつ使う

割引券の使う順番は関係ないから、１枚ずつ使うとしても問題ない。

その商品に割引券を使うべき？

これは、「現時点で最も値段が高い商品」に使うべき。優先度付きキューで管理できる。
計算量は $M$ 回割引券を使い、「現時点で最も値段が高い商品」を探すのに $O(logN)$ かかるので、 $O(MlogN)$ となる。

実装

heapq は最小値を返すので、符号を反転させておくといい
負の切り捨て徐算は値が丸め込まれる方向が違うので、先に正の値に戻しておいた方が楽。（-9 // 2 = -5 になっちゃうよ）

import heapq
N, M = map(int, input().split())
A = list(map(lambda x: -int(x), input().split()))
heapq.heapify(A)

ans = 0
for i in range(M):
    most_expensive = -heapq.heappop(A)
    most_expensive //= 2
    heapq.heappush(A, -most_expensive)

print(-sum(A))