はじめに

AtCoder Beginner Contest 141 （ ABC 141 ）に参加。

D問題でだいぶ躓いてしまったので、解いた方針をまとめておく。

ちなみに、priority_queue の存在を忘れていて、結局 multiset を使って解いた。

この記事では priority_queue を使ったほうでまとめる。

D - Powerful Discount Tickets

N個の品物を買う。
i番目の品物の値段はAi
割引券をM枚持っている
任意の品物に対して任意の枚数の割引券を使うことができる
割引券一枚で半額（小数点以下切り捨て）
最小いくらで買い物ができるか求めよ

atcoder.jp

解いた方針

方針はすぐに立った。

一番値段が高い品物から順々に割引券を使っていけば良い。

問題は実装方法。

一番大きい値段を知るために、常に配列をソートした状態にしたいが、愚直にやるとO(NM)になるはずだからダメ。

だからデータをどの型で扱うかを考える必要がある。

私はmultisetを使って解いたけど、解説を読んだらpriority_queueを使うといいよって書いてあって、「聞いたことある～」とちょっと悲しくなった。

コンテスト中にもっと早く気づきたかった。

cpprefjp.github.io

qiita.com

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main()
{
    // 入力
    ll N, M;
    cin >> N >> M;
    priority_queue<ll> pq; // ソートの状態でデータを保持
    for(int i = 0; i < N; i++)
    {
        ll a;
        cin >> a;
        pq.push(a);
    }
 
    // M回分、最大値を半分に
    for(int i = 0; i < M; i++)
    {
        ll maxv = pq.top() / 2LL;
        pq.pop();
        pq.push(maxv);
    }
 
    // 合計値を計算
    ll sum = 0;
    for(int i = 0; i < N; i++)
    {
        sum += pq.top();
        pq.pop();
    }
 
    // 解を出力
    cout << sum << endl;
    return 0;
}