問題を読み替えつつ 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;
}

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

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

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

問題概要

制約

考えたこと