概要

\(N\) 個の商品を「通常価格」か「セール価格」のどちらかで購入します。セール価格で購入できるのは最大 \(K\) 個までという制限がある中で、合計金額を最小化する問題です。

考察

この問題のポイントは、「クーポンを使うことで、どれだけ安くなるか」という割引額に着目することです。

1. 割引額の計算: 各商品 \(i\) について、通常価格 \(A_i\) とセール価格 \(B_i\) の差を \(D_i = A_i - B_i\) とします。この \(D_i\) は「商品 \(i\) にクーポンを使ったときに得をする金額」を表します。制約より \(A_i \geq B_i\) なので、この値は必ず \(0\) 以上になります。
2. 言い換え: 「合計金額を最小化する」という目的は、「全ての商品を通常価格で購入すると仮定し、そこからクーポンを使って割引額の合計を最大化する」と言い換えることができます。
3. 貪欲法（Greedy）の適用: 割引額 \(D_i\) が大きい商品から順にクーポンを適用していくのが最も効率的です。クーポンは最大 \(K\) 個まで使えるため、割引額が大きい上位 \(K\) 個の商品を選べば、全体の購入金額を最小に抑えることができます。

アルゴリズム

以下の手順で解を求めます。

1. 全ての商品を通常価格で購入したときの合計金額 total_a（\(\sum A_i\)）を計算します。
2. 各商品の割引額 \(D_i = A_i - B_i\) を計算し、リストに格納します。
3. 割引額のリストを降順（大きい順）にソートします。
4. ソートしたリストの先頭から最大 \(K\) 個までの要素の和 max_savings を求めます。
5. total_a - max_savings が求める最小の合計金額となります。

計算量

• 時間計算量: \(O(N \log N)\)
  • 割引額の計算に \(O(N)\)、ソートに \(O(N \log N)\)、上位 \(K\) 個の和の計算に \(O(K)\) かかります。全体ではソートが支配的になります。
• 空間計算量: \(O(N)\)
  • 割引額を保存するためのリストに \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: Pythonで \(N=2 \times 10^5\) 程度の入力を処理する場合、input() を繰り返すよりも sys.stdin.read().split() などで一括で読み込む方が高速です。

• ソートの順序: sort(reverse=True) を使って降順にするか、昇順にソートした後に後ろから \(K\) 個取ることで、割引額の大きいものを選べます。

• スライスの活用: Pythonでは diffs[:k] のようにスライスを使うことで、簡単に上位 \(K\) 個を取り出すことができます。もし \(K > N\) であってもエラーにならず、リストの全要素が対象となるため安全です（本問題の制約では \(K \leq N\) ですが、汎用的な書き方です）。

  ソースコード

import sys

def solve():
    # 標準入力から全てのデータを読み込み、スペースや改行で分割してリストにします
    # 競技プログラミングにおいて、大量の入力を高速に処理する一般的な手法です
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # イテレータを使用してデータを1つずつ取り出します
    it = iter(input_data)
    
    # N: 商品の個数, K: クーポンを使用できる最大個数
    n = int(next(it))
    k = int(next(it))
    
    total_a = 0
    diffs = [0] * n
    
    for i in range(n):
        a = int(next(it))
        b = int(next(it))
        # 全ての商品を通常価格で購入した場合の合計金額を計算
        total_a += a
        # 通常価格とセール価格の差（クーポンによる割引額）を計算
        # 制約より B_i <= A_i なので、この値は必ず0以上になります
        diffs[i] = a - b
        
    # 割引額が大きい順にソートします
    diffs.sort(reverse=True)
    
    # 最大でK個の商品にクーポンを適用できるため、
    # 割引額が大きい方から最大K個を選んで合計金額から差し引きます
    # スライス diffs[:k] は、kがリストの長さを超えても適切に処理されます
    max_savings = sum(diffs[:k])
    
    # 購入金額の合計の最小値を出力
    print(total_a - max_savings)

if __name__ == '__main__':
    solve()

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