今日勉強したことを
つらつらと
logo

abc141_d Powerful Discount Ticketsの解き方の解説 priority_queueの使い方

2020/06/04 13:06
AtCoder Beginner Contest 141のD問題 Powerful Discount Ticketsを解く。

感謝の正拳突き1万回ならぬ、競プロサイトで 1 日 1AC(正解)するように頑張る・・が昨日できなかった。

ABC141 の D 問題 Powerful Discount Ticketsを解いていきます。

高い商品に割引券を使うとお得

すごく問題を単純にして考えてみます。割引券が 1 枚あり、200 円の商品と 50 円の商品がある場合を考えてみます。200 円の商品に使えば 200 / 2 + 50 = 150 円で買えます。

次は 2 枚のパターンを考えてみます。割引券が 2 枚あり、200 円と 50 円の商品がある場合を考えてみます。

1 枚目の割引券を使う先は先ほどと同じく、200 円の商品です。では次は?1 枚割引券を使ったあとの形を考えてみます。1 枚使うと、100 円と 50 円の商品と 1 枚の割引券が残ります。また高い方の 100 円の商品に対して使うと合計 100 円で買えることがわかります。

高い順に並び替え続ける

そういう場合は C++のstd::priority_queueが便利です。

使い方

かんたんなコードで使い方を見てみます。

priority_queue<int> que;
que.push(5);       // pushで追加する
que.push(10);
que.push(4);
cout << que.top(); // 10 topすると、一番大きい値が取れる
que.pop();         // popすると、一番大きい値が消える
cout << que.top(); // 5 10が消えてるので、次に大きい値が取れる

priority_queue を使って、高い順に割引券を使う

高い値を取って、割引券を使って、格納し直す・・というのを繰り返せば AC です。

できあがり

#include <bits/stdc++.h>
using namespace std;

#define ll long long

ll n,m;
int main() {
    priority_queue<ll> q;
    cin >> n >> m;
    for(ll i = 0; i < n; i++) {
        ll tmp;
        cin >> tmp;
        q.push(tmp);
    }
    // 割引券の数だけ回す
    for(ll i = 0; i < m; i++) {
        // 高い値を取って
        ll tmp = q.top();
        q.pop();
        // 割引券を使って、格納し直す
        q.push(tmp / 2);
    }
    ll result = 0;
    // queueから全件取る
    while(!q.empty()) {
        result += q.top();
        q.pop();
    }
    cout << fixed << result;
}

© 2021 simodake