Overview

Calculate the “adjustment cost” to bring each room’s temperature into the range \([L, R]\), then select \(K\) rooms with the smallest costs — the total of these costs is minimized.

Analysis

The minimum cost required to bring each room’s temperature \(T_i\) into the plant-growing range \([L, R]\) is uniquely determined by looking at that room alone.

• If \(T_i < L\), we need to raise it to \(L\), so the cost is \(L - T_i\)
• If \(T_i > R\), we need to lower it to \(R\), so the cost is \(T_i - R\)
• If \(L \le T_i \le R\), no adjustment is needed and the cost is \(0\)

In other words, for each room we can compute the “required cost to use that room” \(c_i\).

The key insight is as follows:

• The only question is which rooms to select, and the optimal adjustment for each selected room is determined independently
• Therefore, the total cost we want to minimize is the minimum sum when choosing \(K\) values from the \(c_i\)
• This is optimally solved by simply taking the \(K\) smallest costs (this can be explained by an exchange argument: if you have selected a room with a larger cost, swapping it with a room that has a smaller cost always improves the solution)

Naively trying all combinations of choosing \(K\) rooms from \(N\) would involve \(\binom{N}{K}\) combinations, which is enormous (impossible when \(N \le 2\times 10^5\)). However, based on the above observation, we can solve it without exhaustive search by computing each room’s cost → sorting → summing the smallest \(K\) values.

Concrete example: - \(L=10, R=20\), temperatures are \([5, 12, 25]\) - \(5\) needs to be raised to \(10\): \(10-5=5\) - \(12\) is within range: \(0\) - \(25\) needs to be lowered to \(20\): \(25-20=5\) Costs are \([5,0,5]\). If \(K=2\), we pick the two smallest: \(0\) and \(5\), for a total of \(5\), which is the minimum.

Algorithm

1. For each room \(i\), compute the adjustment cost \(c_i\) as follows:
   • If \(T_i < L\), then \(c_i = L - T_i\)
   • If \(T_i > R\), then \(c_i = T_i - R\)
   • Otherwise, \(c_i = 0\)
2. Sort the array \(c\) in ascending order
3. Output the sum of the first \(K\) elements: \(\sum_{j=1}^{K} c_{(j)}\) (where \(c_{(j)}\) denotes the values sorted in ascending order)

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(N)\) (for storing the cost array)

Implementation Notes

• The cost computation is the “distance from the range,” and the case analysis reliably includes \(0\)

• Since \(N\) can be large, it is safer to read input quickly using methods like sys.stdin.buffer.read()

• After sorting, the solution can be written concisely as just sum(costs[:K])

  Source Code

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

This editorial was generated by gpt-5.2-high.