概要

各商品の通常価格とセール価格が与えられる中で、最大 \(K\) 個の商品に割引クーポンを使って購入金額の合計を最小にする問題。

考察

各商品について、クーポンを使った場合の「お得度」を考えると、それは通常価格 \(A_i\) とセール価格 \(B_i\) の差 \(A_i - B_i\) に他なりません。つまり、この差が大きい商品にクーポンを使うことで、全体の支払い額をより多く削減できます。

したがって、すべての商品を通常価格で買ったと仮定して合計金額を求め、そこからクーポンを使うことで得られる最大の割引額を引くのが最適です。

素朴な方法として、「すべての商品の部分集合（サイズが \(K\) 以下）に対して、クーポンを使った場合の合計を試す」というのが考えられますが、これは指数時間かかり現実的ではありません。

そこで、差 \(A_i - B_i\) をすべて求め、その大きい順にソートし、上位 \(K\) 個の商品にクーポンを使うのが最適であると分かります。これにより、効率的に最大の節約額を得ることができます。

アルゴリズム

1. 各商品の通常価格の合計 \(total = \sum_{i=1}^{N} A_i\) を計算。
2. 各商品の価格差 \(diff_i = A_i - B_i\) を計算し、リストに保存。
3. このリストを降順にソートする。
4. 上位 \(K\) 個の差分の合計 \(discount = \sum_{i=0}^{K-1} diff_i\) を計算（クーポンによる最大節約額）。
5. 最終的な答えは \(total - discount\)。

例

入力例：

3 2
5 3
8 4
6 5

• 各商品の通常価格の合計：\(5 + 8 + 6 = 19\)
• 各商品の価格差：\([2, 4, 1]\)
• ソート後（降順）：\([4, 2, 1]\)
• 上位 \(K=2\) 個の合計：\(4 + 2 = 6\)
• 節約後の金額：\(19 - 6 = 13\)

計算量

• 時間計算量: \(O(N \log N)\) （ソートが支配的）
• 空間計算量: \(O(N)\) （価格差を保存する配列）

実装のポイント

• sys.stdin.read を使って高速に入力を処理している（Pythonの標準入力が遅いことへの対策）。
• 差分のリストをソートする際に reverse=True を指定して降順にしている。
• クーポンを使える回数が \(K=0\) の場合でも正しく動作する（空のリストに対する sum は0を返す）。

ソースコード

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    K = int(data[1])
    
    products = []
    total = 0
    diffs = []
    
    index = 2
    for _ in range(N):
        A = int(data[index])
        B = int(data[index+1])
        total += A
        diffs.append(A - B)
        index += 2
    
    diffs.sort(reverse=True)
    
    discount = sum(diffs[:K])
    
    result = total - discount
    print(result)

if __name__ == "__main__":
    main()

---

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