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

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

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

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