C++の練習を兼ねて, AtCoder Beginner Contest 141 の 問題D (D – Powerful Discount Tickets) を解いてみた.
■感想.
1. 解説を見る前に解けたので, とりあえず良かったと思う.
2. 一番大きな値段の品物に, 常に割引券を適用すると良さそうに見えたので, その方針で実装して, AC版となった.
本家のサイトABC 141解説をご覧下さい.
■C++版プログラム(問題D／AC版).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#include <bits/stdc++.h> using namespace std; using LL = long long; int main(){ // 1. 入力情報取得. int N, M; scanf("%d %d", &N, &M); priority_queue<LL> pq; for(int i = 0; i < N; i++){ LL a; scanf("%lld", &a); pq.push(a); } // 2. priority_queue の 先頭要素 に, 常に 割引券 を 使用. while(M > 0){ LL a = pq.top(); pq.pop(); a /= 2; // 先頭要素に割引券使用. pq.push(a); // 割引券適用後の金額を追加. M--; } // 3. すべての品物を買うために必要なお金の最小値は？ LL ans = 0; while(!pq.empty()){ LL a = pq.top(); pq.pop(); ans += a; } // 4. 出力 ～ 後処理. printf("%lld\n", ans); return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
[入力例] 3 3 2 13 8 [出力例] 9 ※AtCoderテストケースより [入力例] 4 4 1 9 3 5 [出力例] 6 ※AtCoderテストケースより [入力例] 1 100000 1000000000 [出力例] 0 ※AtCoderテストケースより [入力例] 10 1 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 [出力例] 9500000000 ※AtCoderテストケースより [入力例] 30 17 111 3333 66666 11111 77777 2222 888 555 333 4444 22222 88888 777 444 33333 5555 666 55555 1111 6666 7777 666 222 9999 44444 1215 8888 1353 99999 999 [出力例] 172109 |
■参照サイト
AtCoder Beginner Contest 141