AtCoder ABC 246 C - Coupon (灰色, 300 点)

ソートが必要になるところが少し難しいかもしれない。

• 問題へのリンク

問題概要

個の商品があって、それぞれ 円である。

またクーポンが 枚あって、1 枚のクーポンを使って次のことができる。

• 商品を 1 つ選ぶ
• その商品の価格を 円減少させる
• ただしもとの価格が 円未満の場合は、0 円にする

クーポンを効率よく活用したとき、 個の商品をすべて購入するのに要する最小費用を求めよ。

制約

• 
• 

手を動かしてみる

まずは手を動かして問題の様子をつかんでみよう。たとえば で , としてみよう。

このとき、たとえばまず 1 個目の商品にクーポンを適用してみよう。そうすると 2 回適用することで価格は、

12 → 7 → 2

となる。このときさらにクーポンを適用するのは少しもったいない。なぜならその場合、

• 1 回目のクーポンによる価格減少分は、12 → 7 で「-5」
• 2 回目のクーポンによる価格減少分は、7 → 2 で「-5」
• 3 回目のクーポンによる価格減少分は、2 → 0 で「-2」

ということになる。1, 2 回目は「-5」を達成したのに対して、3 回目は「-2」にとどまってしまう。

それをするくらいなら、2 個目の商品の 16 円にクーポンを適用した方がいい。そうすることで「-5」の達成を継続できる。

最後のあまりを処理

以上の話を一般化しよう。一般に「$-X$ 円」を達成できるところを優先的に減らしていこう。具体的には、各 に対して、A[i] / X (あまりを切り捨てた値) の総和回だけ「$-X$ 円」を実施できることになる。

この総和を としたとき、もし ならば、 回のクーポンはすべて「$-X$ 円」を達成できるので、それが答えになる。

よって の場合を考えよう。この場合、まずは「$-X$ 円」を達成できる部分は使い切ってしまおう。そうすると

• K -= S
• 各 i に対して A[i] %= X

という状態になったものと考えてよい。たとえば , , のとき、下図のように、、 の問題に帰着される。

こうなったら、余ったクーポンを有効活用するために、「減らせる金額が大きいところを優先的に使っていく」のがよいと言える。具体的には次のように求められる。

---

• 配列 A (あまりを取った値) を大きい順にソートして
• 大きい順に 個を 0 にする (ただし の場合はすべて 0 にして終了)
• 残った A の総和が答え

---

計算量は「ソート」に最も時間がかかるので、。

コード

#include <bits/stdc++.h>
using namespace std;

long long solve() {
    // 入力 (sum は最初の総額)
    long long N, K, X, sum = 0;
    cin >> N >> K >> X;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i], sum += A[i];

    // 「-X」を適用できるところを先に適用してしまう
    long long S = 0;
    vector<long long> amari(N);
    for (int i = 0; i < N; ++i) {
        S += A[i] / X;
        A[i] %= X;
    }

    // S >= K のときはすべてのクーポンを
    if (S >= K) return sum - K * X;

    // K > S のときは、減らせる金額が大きいところを優先的に
    K -= S;
    sort(A.begin(), A.end(), greater<long long>());
    for (int i = 0; i < min(N, K); ++i) A[i] = 0;
    long long res = 0;
    for (int i = 0; i < N; ++i) res += A[i];
    return res;
}

int main() {
    cout << solve() << endl;
}

類題情報

似た感じで解ける問題！

drken1215.hatenablog.com