Overview

This problem asks for the minimum cost to select \(K\) out of \(N\) rooms and adjust each room’s temperature to be within the appropriate range \([L, R]\). It can be solved using a greedy approach: calculate the adjustment cost for each room and select the \(K\) rooms with the smallest costs.

Analysis

Key Observations

1. The cost for each room can be calculated independently

   • The cost to adjust room \(i\)’s temperature \(T_i\) to fall within the range \([L, R]\) does not depend on the state of other rooms

2. How to adjust with minimum cost

   • If \(T_i < L\): raise to \(L\) for minimum cost → cost is \(L - T_i\)
   • If \(T_i > R\): lower to \(R\) for minimum cost → cost is \(T_i - R\)
   • If \(L \leq T_i \leq R\): no adjustment needed → cost is \(0\)

3. Which \(K\) rooms should we select?

   • Since we want to minimize the total cost, we should preferentially select rooms with smaller costs

Concrete Example

For example, with \(N=5\), \(K=3\), \(L=20\), \(R=25\), \(T = [15, 22, 30, 18, 24]\): - Room 1: \(T_1=15 < 20\) → cost \(= 20 - 15 = 5\) - Room 2: \(T_2=22\) is within range → cost \(= 0\) - Room 3: \(T_3=30 > 25\) → cost \(= 30 - 25 = 5\) - Room 4: \(T_4=18 < 20\) → cost \(= 20 - 18 = 2\) - Room 5: \(T_5=24\) is within range → cost \(= 0\)

Sorted costs: \([0, 0, 2, 5, 5]\)

Selecting 3 with the smallest costs gives a total cost of \(0 + 0 + 2 = 2\).

Algorithm

1. For each room, calculate the cost to adjust the temperature to the range \([L, R]\)
2. Sort the cost array in ascending order
3. Sum the first \(K\) elements of the sorted array

This method is called a greedy algorithm, a technique that “obtains the globally optimal solution by repeatedly making locally optimal choices.” In this problem, it is guaranteed that selecting rooms with smaller costs is always optimal.

Complexity

• Time complexity: \(O(N \log N)\)

  • Cost calculation for each room: \(O(N)\)
  • Sorting: \(O(N \log N)\)
  • Sum of the first \(K\) elements: \(O(K) \subseteq O(N)\)

• Space complexity: \(O(N)\)

  • \(O(N)\) for the array storing costs

Implementation Notes

• Note that temperature \(T_i\) and the range bounds \(L, R\) can be negative (down to \(-10^9\)). However, since costs are always non-negative, no special handling is required
• The maximum cost is around \(2 \times 10^9\), and the sum of \(K\) costs can be up to around \(2 \times 10^{14}\), which may overflow 32-bit integers. In Python, there’s no need to worry about integer overflow
• After sorting with costs.sort(), using the slice costs[:K] to extract the first \(K\) elements is idiomatic Python

Source Code

def solve():
    N, K, L, R = map(int, input().split())
    T = list(map(int, input().split()))
    
    # Calculate the cost for each room
    # If temperature is between L and R inclusive, cost is 0; if below L, cost is L-Ti; if above R, cost is Ti-R
    costs = []
    for t in T:
        if t < L:
            costs.append(L - t)
        elif t > R:
            costs.append(t - R)
        else:
            costs.append(0)
    
    # Select K rooms with the smallest costs
    costs.sort()
    print(sum(costs[:K]))

solve()

This editorial was generated by claude4.5opus.