概要

各部屋を温度範囲 \([L, R]\) に入れるための「調整コスト」を計算し、そのコストが小さい部屋から \(K\) 個選んだときの合計が最小になります。

考察

各部屋の温度 \(T_i\) を植物が育つ範囲 \([L, R]\) に収めるために必要な最小コストは、その部屋だけを見れば一意に決まります。

• もし \(T_i < L\) なら、\(L\) まで上げればよいのでコストは \(L - T_i\)
• もし \(T_i > R\) なら、\(R\) まで下げればよいのでコストは \(T_i - R\)
• もし \(L \le T_i \le R\) なら、調整不要でコストは \(0\)

つまり、各部屋に対して「その部屋を使うための必要コスト」\(c_i\) が求まります。

ここで重要な気づきは次の通りです。

• どの部屋を選ぶかだけが問題で、選んだ後の最適調整は各部屋で独立に決まる
  
• よって、最小化したい総コストは \(c_i\) の中から \(K\) 個選んだときの和の最小 になる
  
• これは単に コストが小さい順に \(K\) 個取れば最適（交換法で説明できます。大きいコストを選んでいるなら、それより小さいコストの部屋に入れ替えた方が必ず良い）

素朴に「\(N\) 個から \(K\) 個選ぶ組合せ」を全探索すると、組合せ数は \(\binom{N}{K}\) で巨大（\(N \le 2\times 10^5\) では不可能）です。
しかし上の観察により、全探索せずに 各部屋のコスト計算 → ソート → 小さい \(K\) 個を加算 で解けます。

具体例： - \(L=10, R=20\), 温度が \([5, 12, 25]\) のとき
- \(5\) は \(10\) まで上げる：\(10-5=5\)
- \(12\) は範囲内：\(0\)
- \(25\) は \(20\) まで下げる：\(25-20=5\)
コストは \([5,0,5]\)。\(K=2\) なら小さい順に \(0,5\) を選んで合計 \(5\) が最小です。

アルゴリズム

1. 各部屋 \(i\) について調整コスト \(c_i\) を次で求める：
   • \(T_i < L\) なら \(c_i = L - T_i\)
   • \(T_i > R\) なら \(c_i = T_i - R\)
   • それ以外は \(c_i = 0\)
2. 配列 \(c\) を昇順ソートする
3. 先頭から \(K\) 個の和 \(\sum_{j=1}^{K} c_{(j)}\) を出力する（\(c_{(j)}\) は小さい順に並べた値）

計算量

• 時間計算量: \(O(N \log N)\)（ソートが支配的）
• 空間計算量: \(O(N)\)（コスト配列を保持）

実装のポイント

• コスト計算は「範囲からの距離」になっており、場合分けで確実に \(0\) を含める
  

• \(N\) が大きいので、入力は sys.stdin.buffer.read() などで高速に読むと安全
  

• ソート後に sum(costs[:K]) とするだけで簡潔に書ける

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, K, L, R = data[0], data[1], data[2], data[3]
    T = data[4:]

    costs = []
    for x in T:
        if x < L:
            costs.append(L - x)
        elif x > R:
            costs.append(x - R)
        else:
            costs.append(0)

    costs.sort()
    print(sum(costs[:K]))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。