概要

\(N\) 個の商品のうち、価格が高い順に最大 \(K\) 個を無料にできるクーポンを使い、支払う金額の合計を最小にする問題。

考察

この問題では、支払う合計金額を最小にしたいので、価格が高い商品をクーポンで無料にするのが最も効果的です。

例えば、商品の価格が \([100, 200, 300]\) 円で、クーポンを \(1\) 回使える場合、最も高い \(300\) 円の商品を無料にすれば、支払いは \(100 + 200 = 300\) 円になります。

したがって、価格のリストを降順にソートして、上位 \(K\) 個の商品を無料にするのが最適です。残りの商品（\(K\) 番目より後ろ）の価格の合計が答えになります。

もし素朴に「どの商品を選ぶか全探索」しようとすると、組み合わせが非常に多くなり、時間内に解けません（TLE）。しかし、この問題は単純に「価格が高いものから \(K\) 個無料にする」だけで最適解が得られるため、ソートを使って効率的に解くことができます。

アルゴリズム

1. 商品の価格リスト \(D\) を読み込む。
2. 価格リストを降順にソートする（高い価格が先頭に来る）。
3. ソート後のリストにおいて、インデックス \(K\) 以降の要素（つまり無料にならない商品）の合計を求める。
4. その合計を出力する。

たとえば、\(D = [100, 200, 300], K = 1\) のとき： - ソート後：\([300, 200, 100]\) - インデックス \(1\) 以降の合計：\(200 + 100 = 300\)

計算量

• 時間計算量: \(O(N \log N)\) （ソートに dominate）
• 空間計算量: \(O(N)\) （入力リストの保持）

実装のポイント

• sort(reverse=True) で降順ソートを行う。
• 合計は sum(D[K:]) で簡単に求められる。
• \(K > N\) の場合でも、スライス範囲外エラーは発生しない（空のリストに対する sum は 0 になる）。

ソースコード

N, K = map(int, input().split())
D = list(map(int, input().split()))

D.sort(reverse=True)

ans = sum(D[K:])
print(ans)

この解説は qwen3-coder-480b によって生成されました。