Overview

Select \(K\) out of \(N\) rooms and find the minimum cost to adjust each of their temperatures to be within the range \([L, R]\).

Analysis

For each room’s current temperature \(T_i\), adjustment is needed if it falls outside the range \([L, R]\). Specifically:

• If \(T_i < L\), the temperature needs to be raised by \(L - T_i\) degrees, costing \(L - T_i\)
• If \(T_i > R\), the temperature needs to be lowered by \(T_i - R\) degrees, costing \(T_i - R\)
• If \(L \leq T_i \leq R\), no adjustment is needed, and the cost is \(0\)

Therefore, the adjustment cost for each room can be computed in advance.

A naive approach of “trying all combinations of choosing \(K\) rooms and computing the total cost” would involve far too many combinations and is not practical (exponential time complexity).

However, in this problem, the optimal solution can be obtained not by considering “which rooms to select” but simply by “selecting the top \(K\) rooms with the lowest adjustment costs.” This is a greedy approach.

In other words, we compute the adjustment cost for all rooms and then select the \(K\) rooms with the smallest costs in ascending order.

Algorithm

1. For each room’s temperature \(T_i\), compute the required adjustment cost if it is outside the range \([L, R]\), and store it in the list costs.
2. Sort costs in ascending order.
3. Sum the first \(K\) costs and output the result.

For example, given the following input:

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

The adjustment costs are: - Room 1: \(20 - 15 = 5\) - Room 2: \(0\) (within range) - Room 3: \(35 - 30 = 5\) - Room 4: \(20 - 18 = 2\) - Room 5: \(0\)

The cost list is [5, 0, 5, 2, 0] → after sorting: [0, 0, 2, 5, 5]
Selecting the first 3 gives a total cost of \(0 + 0 + 2 = 2\)

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(N)\) (size of the cost list)

Implementation Notes

• Ensure the conditional branching for whether the temperature is within range is written correctly.

• In Python, sort() is a stable sort, so the order of elements with the same value is preserved, which is not a concern here.

• sys.stdin.read is used for fast input reading (important when standard input is large).

  Source Code

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

---

This editorial was generated by qwen3-coder-480b.