けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 141 D - Powerful Discount Tickets (2Q, 緑色, 400 点)

AtCoder AtCoder400点 ABC-D Greedy 操作 操作をK回まで行える 数列 priority_queue データ構造 考察：操作・条件・目的関数を言い換える 最適化の考察：変形しても悪化しない Greedy:交換しても悪化しない 緑色diff 価格に関する問題 魔法を唱える問題 NoviSteps2Q Greedy:後によいものを残す・今が良いほど未来も良い

問題を読み替えつつ Greedy！！！

問題へのリンク

問題概要

N 個の品物があって、それぞれ A_1, \dots, A_N 円で売られている。今 M 枚の魔法の割引券があって、品物を買う際に割引券を好きな枚数使うことができる。

X 円の品物を買う際に Y 枚の割引券を使った場合、その品物を X / 2^{Y} 円で買うことができる (割り切れない分は切り捨て)。

上手に割引券を適用したときの N 個の品物の価格の総和の最小値を求めよ。

制約

  • 1 \le N, M \le 10^{5}

考えたこと

ようは

「 N 個の整数から 1 個選んで 2 で割る (割り切れない分は切り捨て)」という操作を M 回行える。

合計値を最小化せよ

という問題だと思うことができる。こういう「操作が M 回まで行えるので結果を最適化してください」という問題は、ほぼほぼ何らかの Greedy 構造があるイメージ。

今回は比較的明らかで、毎回「 N 数のうちの最大値を 2 で割る」とすればよい。理由は、最大値を放置することとした場合のいかなる解に対しても、最大値を 2 で割った場合の方が悪くないようにできるから。

実装上は最大値を毎回高速に求めるために、priority_queue を用いるとよい。

  • 最大値を pop して
  • 2 で割って
  • また push する

というのを M 回繰り返す。計算量は O((M + N)\log{N})。

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    int N, M; cin >> N >> M;

    priority_queue<long long> que;
    for (int i = 0; i < N; ++i) {
        long long A; cin >> A; que.push(A);
    }
    for (int i = 0; i < M; ++i) {
        long long t = que.top(); que.pop();
        que.push(t/2);
    }
    long long res = 0;
    while (!que.empty()) res += que.top(), que.pop();
    cout << res << endl;
}