概要

\(N\) 個の商品の中から最大 \(K\) 個を選んで価格を \(0\) 円にできるとき、支払う合計金額を最小化する問題です。

考察

支払う合計金額を最小にするためには、「クーポンを使って安くできる金額（割引額）を最大にする」ことを考えます。

クーポンは \(1\) 枚につき \(1\) つの商品の価格を \(0\) 円にします。したがって、価格が \(1000\) 円の商品にクーポンを使えば \(1000\) 円得をしますが、 \(100\) 円の商品に使っても \(100\) 円しか得をしません。

このことから、以下の戦略が最適であることがわかります。 - 価格が高い順に \(K\) 個の商品を選び、それらにクーポンを適用する。

もし商品の数 \(N\) よりもクーポンの数 \(K\) の方が多い場合は、すべての商品を \(0\) 円にできるため、合計金額は \(0\) 円になります。

アルゴリズム

1. 商品の価格リスト \(D\) を受け取る。
2. リスト \(D\) を降順（大きい順）にソートする。
3. 先頭から \(K\) 個の商品を除外する（または \(0\) 円とみなす）。
4. 残った商品の価格を合計する。

具体例として、\(N=5, K=2\)、価格が \([100, 500, 200, 800, 300]\) の場合を考えます。 - 降順にソートすると \([800, 500, 300, 200, 100]\) となります。 - 高い方から \(2\) つ（\(800\) 円と \(500\) 円）にクーポンを使います。 - 残った \([300, 200, 100]\) の合計である \(600\) 円が答えとなります。

計算量

• 時間計算量: \(O(N \log N)\)
  • 商品の価格のソートに \(O(N \log N)\) かかります。その後の合計計算は \(O(N)\) なので、ソートの計算量が支配的になります。
• 空間計算量: \(O(N)\)
  • 商品の価格を保持するために長さ \(N\) のリストを使用します。

実装のポイント

• Pythonでは list.sort(reverse=True) を使うことで、簡単に降順ソートが行えます。

• sum(d[k:]) のようにスライスを用いることで、「\(K\) 番目以降の要素のみを合計する」という処理を簡潔に記述できます。\(K \geq N\) の場合、スライス d[k:] は空のリストを返すため、結果は正しく \(0\) となります。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを取得し、スペース区切りで分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 商品の数, K: クーポンの最大使用回数
    n = int(input_data[0])
    k = int(input_data[1])
    
    # D: 各商品の価格リスト
    d = list(map(int, input_data[2:]))
    
    # 支払う合計金額を最小化するためには、価格が高い商品から順にクーポンを適用するのが最適です。
    # 商品の価格を降順（大きい順）にソートします。
    d.sort(reverse=True)
    
    # クーポンは最大 K 個の商品を 0 円にできるため、
    # 価格が高い方から K 個を除いた残りの商品の合計金額が、支払う最小金額となります。
    # スライス d[k:] を使うことで、インデックス K 以降（K+1番目以降の商品）を取得できます。
    # もし K >= N の場合、d[k:] は空リストになり、sum は 0 を返します。
    ans = sum(d[k:])
    
    # 結果を出力します
    print(ans)

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-preview によって生成されました。