概要

\(N\) 個の部屋のうち \(K\) 個を選び、それぞれの室温を \([L, R]\) の範囲内に調整するための最小コストを求めます。

考察

各部屋の現在の温度 \(T_i\) に対し、範囲 \([L, R]\) の外にある場合、調整が必要になります。具体的には：

• \(T_i < L\) のとき、\(L - T_i\) 度上げる必要があり、コストは \(L - T_i\)
• \(T_i > R\) のとき、\(T_i - R\) 度下げる必要があり、コストは \(T_i - R\)
• \(L \leq T_i \leq R\) のときは調整不要で、コストは \(0\)

したがって、各部屋について調整コストを前もって計算しておくことができます。

素朴な方法として、「すべての組み合わせから \(K\) 個選んでコストの合計を求める」というのは、組み合わせが非常に多く、現実的ではありません（計算量は指数時間）。

しかし、この問題では「どの部屋を選ぶか」ではなく「調整コストが最も少ない上位 \(K\) 個を選ぶ」だけで最適解が得られます。これは貪欲法の考え方です。

つまり、すべての部屋の調整コストを計算し、その中からコストが小さい順に \(K\) 個選べばよいのです。

アルゴリズム

1. 各部屋の温度 \(T_i\) に対して、範囲 \([L, R]\) 外であれば必要な調整コストを計算し、リスト costs に格納します。
2. costs を昇順にソートします。
3. 先頭 \(K\) 個のコストを合計し、出力します。

例えば、入力が以下の場合：

N=5, K=3, L=20, R=30
T = [15, 25, 35, 18, 28]

調整コストはそれぞれ： - 部屋1: \(20 - 15 = 5\) - 部屋2: \(0\)（範囲内） - 部屋3: \(35 - 30 = 5\) - 部屋4: \(20 - 18 = 2\) - 部屋5: \(0\)

コストリストは [5, 0, 5, 2, 0] → ソートすると [0, 0, 2, 5, 5]
先頭3つを選ぶとコスト合計は \(0 + 0 + 2 = 2\)

計算量

• 時間計算量: \(O(N \log N)\)（ソートに支配される）
• 空間計算量: \(O(N)\)（コストリストのサイズ）

実装のポイント

• 温度が範囲内かどうかの条件分岐を正確に記述すること。

• Python では sort() が安定ソートであり、同じ値の要素の順序は保たれるので、特に気にする必要はない。

• 入力を高速に読み込むために sys.stdin.read を使用している（標準入力が大きい場合に重要）。

  ソースコード

import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    L = int(data[2])
    R = int(data[3])
    
    T = list(map(int, data[4:4+N]))
    
    # 各部屋の調整コストを計算
    costs = []
    for t in T:
        if t < L:
            cost = L - t
        elif t > R:
            cost = t - R
        else:
            cost = 0
        costs.append(cost)
    
    # コストが小さい順にK個選ぶ
    costs.sort()
    total_cost = sum(costs[:K])
    
    print(total_cost)

if __name__ == "__main__":
    main()

---

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