AtCoder Beginner Contest 141 [ D - Powerful Discount Tickets ]をPythonで解く(400点、🟩緑diff)
問題
解法
問題を一見すると
「どの商品に何枚半額割引券を使えばよいか?」
という問題に見える。
だが半額割引券を1枚ずつ使っても結果は変わらない。
なので、
「一番値段が高い商品に1枚ずつ割引券を使う」
という貪欲法で解ける。
あとは、これを高速に処理すれば良いが、優先度付きキュー(priority queue)を使う。
優先度付きキューは、最小値を高速にとることができるので、全ての数字に-1をかけて負の数字として扱い、最小値を半額していくロジックにする。
負の値を//2で割り算切り捨てすると結果にズレが出るので正の値で//2にする。