概要

\(N\) 個の部屋の中から \(K\) 個を選び、それぞれの室温を範囲 \([L, R]\) 内に収めるために必要な合計コストの最小値を求める問題です。

考察

この問題を解くためのポイントは、「各部屋を個別に見たときの最小コスト」と「どの部屋を選ぶべきか」の2点に分解して考えることです。

1. 各部屋を調整するための最小コスト

ある部屋の現在の室温を \(T_i\) としたとき、その部屋を範囲 \([L, R]\) 内にするための最小コスト \(C_i\) は以下のように計算できます。

• \(T_i < L\) の場合: 室温が低すぎるため、 \(L\) 度まで上げる必要があります。コストは \(C_i = L - T_i\) です。
• \(T_i > R\) の場合: 室温が高すぎるため、 \(R\) 度まで下げる必要があります。コストは \(C_i = T_i - R\) です。
• \(L \leq T_i \leq R\) の場合: すでに範囲内のため、調整は不要です。コストは \(C_i = 0\) です。

2. どの部屋を \(K\) 個選ぶべきか

各部屋の調整コスト \(C_i\) が求まれば、あとは合計コストが最小になるように \(K\) 個の部屋を選ぶだけです。 各部屋のコストは互いに独立している（ある部屋の温度を変えても他の部屋のコストは変わらない）ため、「コスト \(C_i\) が小さい順に \(K\) 個選ぶ」という貪欲な戦略が最適となります。

もしコストが大きい部屋をわざわざ選んでしまうと、それをコストの小さい部屋に置き換えることで必ず合計コストを減らす（あるいは維持する）ことができるからです。

アルゴリズム

1. 各部屋 \(i = 1, 2, \ldots, N\) について、調整コスト \(C_i\) を計算し、配列（リスト）に格納します。
2. 配列 \(C\) を昇順（小さい順）にソートします。
3. ソートされた配列の先頭から \(K\) 個の要素の和を計算し、出力します。

計算量

• 時間計算量: \(O(N \log N)\)
  • 各部屋のコスト計算に \(O(N)\)、コストのソートに \(O(N \log N)\)、先頭 \(K\) 個の和の計算に \(O(K)\) かかります。全体ではソートが支配的となり \(O(N \log N)\) です。制約の \(N = 2 \times 10^5\) に対して十分高速に動作します。
• 空間計算量: \(O(N)\)
  • 各部屋のコストを保持するために長さ \(N\) の配列を使用します。

実装のポイント

• 入力の高速化: \(N\) や \(T_i\) の数が多いため、Pythonでは sys.stdin.read().split() などを用いて一括で入力を取得すると実行時間を短縮できます。

• 大きな値の扱い: 室温やコストの値が \(10^9\) を超える可能性がありますが、Pythonは標準で多倍長整数をサポートしているため、オーバーフローを気にせず計算できます。

  ソースコード

import sys

def solve():
    # 入力を一括で読み込み、スペースや改行で分割します。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 部屋の数, K: 選ぶ部屋の数, L: 室温の下限, R: 室温の上限
    N = int(input_data[0])
    K = int(input_data[1])
    L = int(input_data[2])
    R = int(input_data[3])
    
    # 各部屋の現在の室温 T_i を取得し、[L, R] の範囲に調整するためのコストを計算します。
    costs = []
    for i in range(N):
        ti = int(input_data[i + 4])
        if ti < L:
            # 室温が L 未満の場合、L まで上げる必要がある
            costs.append(L - ti)
        elif ti > R:
            # 室温が R より高い場合、R まで下げる必要がある
            costs.append(ti - R)
        else:
            # すでに範囲内の場合、コストは 0
            costs.append(0)
    
    # コストが小さい順に K 個の部屋を選ぶのが最適です。
    costs.sort()
    
    # 最小の総コストを計算して出力します。
    print(sum(costs[:K]))

if __name__ == '__main__':
    solve()

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