Overview

Given \(N\) rooms, select \(K\) of them and find the minimum total cost required to bring each selected room’s temperature within the range \([L, R]\).

Analysis

The key to solving this problem is to break it down into two parts: “the minimum cost to adjust each individual room” and “which rooms should be selected”.

1. Minimum Cost to Adjust Each Room

Given that a room’s current temperature is \(T_i\), the minimum cost \(C_i\) to bring that room’s temperature within the range \([L, R]\) can be calculated as follows:

• If \(T_i < L\): The temperature is too low, so it needs to be raised to \(L\) degrees. The cost is \(C_i = L - T_i\).
• If \(T_i > R\): The temperature is too high, so it needs to be lowered to \(R\) degrees. The cost is \(C_i = T_i - R\).
• If \(L \leq T_i \leq R\): The temperature is already within range, so no adjustment is needed. The cost is \(C_i = 0\).

2. Which \(K\) Rooms Should Be Selected

Once the adjustment cost \(C_i\) for each room is determined, we simply need to select \(K\) rooms that minimize the total cost. Since each room’s cost is independent of the others (changing one room’s temperature does not affect the cost of other rooms), the greedy strategy of “selecting the \(K\) rooms with the smallest costs \(C_i\)” is optimal.

If we were to select a room with a higher cost, we could always reduce (or maintain) the total cost by replacing it with a room that has a lower cost.

Algorithm

1. For each room \(i = 1, 2, \ldots, N\), calculate the adjustment cost \(C_i\) and store it in an array (list).
2. Sort the array \(C\) in ascending order (from smallest to largest).
3. Compute the sum of the first \(K\) elements of the sorted array and output the result.

Complexity

• Time Complexity: \(O(N \log N)\)
  • Computing each room’s cost takes \(O(N)\), sorting the costs takes \(O(N \log N)\), and summing the first \(K\) elements takes \(O(K)\). Overall, sorting dominates, giving \(O(N \log N)\). This runs sufficiently fast for the constraint \(N = 2 \times 10^5\).
• Space Complexity: \(O(N)\)
  • An array of length \(N\) is used to store the cost of each room.

Implementation Notes

• Fast Input: Since \(N\) and the number of \(T_i\) values can be large, in Python you can reduce execution time by reading all input at once using sys.stdin.read().split().

• Handling Large Values: Temperatures and costs may exceed \(10^9\), but Python natively supports arbitrary-precision integers, so there is no need to worry about overflow.

  Source Code

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()

This editorial was generated by gemini-3-flash-preview.