昨日@buriodenさんが開催しているバチャコンに参加してました。結果からいうと3完だったのですが、Dの問題が解けなくて終わった後に解説ACしました。その復習としてここでまとめようと思います。
リンクはこちらから
①考え方
支払う値段をどのくらい小さくできるかっていうのがこの問題の趣旨です。
ではどのようにしてそのようなプログラムを書くのでしょうか？
この問題について考えていくと
以下のようなことがわかると思います。
一番高い品物の値段を2で割っていけば良い
ということです。
入力例1で確認してみましょう
N = 3
M = 3
A = [2, 13, 8]
1. 大きい順にします
13 8 2
2. 13を2で割ります
6 8 2
13を2で割ったのでMを1減らします
M = 2
3. 大きい順にします
8 6 2
4. 8を2で割ります
4 6 2
8を2で割ったのでMを1減らします
M = 1
5. 大きい順にします
6 4 2
6. 6を2で割ります
3 4 2
6を2で割ったのでMを1減らします
M = 0
Mが0になったので操作を終了します。
という感じの操作をするためのコードを書きたいわけです。
その時に何をすればいいかと言いますと...
priority_queue
を使えばいいのです。
これを使うことで何ができるかと言うと
毎回ソートすることなく最大値にアクセス可能なことです。
（毎回ソートしてると実行時間に間に合わなくなります。）
ではこれを用いて書いていきましょう！
実装例1
#include <bits/stdc++.h>
using namespace std;
int main() {
int N, M;
priority_queue<int> A;
for(int i=0; i<N; i++) {
int x;
cin >> x;
A.push(x);
}
while(M > 0) {
int x = A.top();
x /= 2;
A.pop();
A.push(x);
M--;
}
}
priority_queueの使い方に関しては以下のサイトを見ると良いと思います。
そして最後にAが空になるまで足していくという操作をおこないます。
その方法は（ans = 0としておきます）
Aの最大値にアクセスしそれをansに足していき取り出します。
実装例2
#include <bits/stdc++.h>
using namespace std;
int main() {
priority_queue<int> A;
long long ans = 0;
while(!A.empty()) {
ans += A.top();
A.pop();
}
cout << ans << endl;
}
おそらく大丈夫かもしれませんが、あえてlong long型にしておきました。
②提出したコード
#include <bits/stdc++.h>
using namespace std;
int main() {
int N, M;
cin >> N >> M;
priority_queue<int> A;
for(int i=0; i<N; i++) {
int x;
cin >> x;
A.push(x);
}
while(M > 0) {
int x = A.top();
x /= 2;
A.pop();
A.push(x);
M--;
}
long long ans = 0;
while(!A.empty()) {
ans += A.top();
A.pop();
}
cout << ans << endl;
return 0;
}
import io
import sys
import statistics
import math
import queue
import heapq
N, M = map(int, input().split())
A = list(map(int, input().split()))
A = list(map(lambda x: x*(-1), A))
heapq.heapify(A)
while M > 0:
x = heapq.heappop(A) * (-1)
x = x // 2
heapq.heappush(A, x * (-1))
M -= 1
print(sum(A)*(-1))
③まとめ
この問題ではpriority_queueを使う練習の問題かと個人的に思ってます。①考え方の方にもありますが、これを使うのは毎回ソートすることなく最大値にアクセスして2で割ってあげたいからです。ということで、次は解けるようにしたいですね。参考文献にpriority_queue関連の記事載せておきます。
ここまでお読みいただきありがとうございました！
④参考文献