abc141_d Powerful Discount Ticketsの解き方の解説 priority_queueの使い方
2020/06/04 13:06
感謝の正拳突き１万回ならぬ、競プロサイトで 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;
}