概要

最大 \(K\) 個まで選んだ商品の価格を \(0\) 円にできるとき、支払う合計金額を最小にするには「高い商品から順にクーポンを使う」のが最適です。

考察

クーポンを使うと、その商品の支払いがそのまま減ります。つまり、商品 \(i\) にクーポンを使うことで得られる「割引額」はちょうど \(D_i\) 円です。
よって、合計金額を最小化することは「割引額の合計を最大化すること」と同じです。

ここで重要な気づきは次の通りです。

• クーポンを使う商品を \(K\) 個選ぶとき、割引額合計は選んだ商品の価格の合計になる
• 割引額合計を最大にするには、価格が大きい商品を優先して選べばよい（貪欲に最大から取る）

例えば \(D=[5, 2, 9, 4]\)、\(K=2\) のとき、 - 高い順に \(9\) と \(5\) に使うと割引額は \(14\)、支払いは \((5+2+9+4)-14=6\) - もし \(5\) と \(4\) に使うと割引額は \(9\)、支払いは \(20-9=11\)
となり、高い商品に使うほど得です。

素朴に「どの商品にクーポンを使うか」を全探索すると、組合せは \({N \choose K}\) 通りで \(N \le 2\times 10^5\) では到底間に合いません。
そこで「価格の大きい順に \(K\) 個選ぶ」という貪欲法に落とし込み、ソートで解決します。

アルゴリズム

1. 価格配列 \(D\) の総和 \(S=\sum D_i\) を求める。
2. \(D\) を降順にソートする。
3. 先頭 \(K\) 個（最も高い \(K\) 個）の和 \(T\) を求める。
4. 答えは \(S-T\)。

※ \(K=0\) のときは何も割引できないので、そのまま \(S\) を出力します。

計算量

• 時間計算量: ソートが支配的なので \(O(N \log N)\)
• 空間計算量: 配列を保持するため \(O(N)\)

実装のポイント

• \(D_i\) は最大 \(10^9\)、\(N\) は最大 \(2\times 10^5\) なので、合計は最大で \(2\times 10^{14}\) 程度になります。Python の int なら安全に扱えます。

• D.sort(reverse=True) で降順ソートし、sum(D[:K]) で上位 \(K\) 個の合計を取ると簡潔に書けます。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    D = list(map(int, input().split()))
    total = sum(D)
    if K == 0:
        print(total)
        return
    D.sort(reverse=True)
    print(total - sum(D[:K]))

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。