Overview

Given \(N\) classrooms where you can install air conditioners in at most \(M\) of them to reduce their deterioration level to \(0\), the problem asks to minimize the maximum deterioration level among the remaining classrooms. The optimal strategy is to prioritize installing air conditioners in classrooms with the highest deterioration levels.

Analysis

Key Insight: Greedy Approach is Optimal

Since we want to minimize the maximum value of deterioration levels, we should prioritize installing air conditioners in classrooms with higher deterioration levels.

Let’s consider a concrete example. For \(N = 5, M = 2\) with deterioration levels \([3, 7, 1, 9, 5]\):

• Sorting deterioration levels in descending order gives \([9, 7, 5, 3, 1]\)
• Install \(2\) air conditioners in the top \(2\) classrooms with the highest deterioration (levels \(9\) and \(7\))
• After installation, the deterioration levels become \([0, 0, 5, 3, 1]\)
• The maximum value is \(5\)

If we installed in different classrooms, values like \(9\) or \(7\) would remain, resulting in a larger maximum.

The Answer is the \(M\)-th Element After Sorting

When deterioration levels are sorted in descending order and air conditioners are installed in the top \(M\) classrooms, the maximum deterioration level among the remaining classrooms is the \((M+1)\)-th element in descending order (i.e., \(D[M]\) in 0-indexed).

Special Case

When \(M \geq N\), air conditioners can be installed in all classrooms, so the answer is \(0\).

Algorithm

1. Sort the deterioration level array \(D\) in descending order.
2. If \(M \geq N\), air conditioners can be placed in all classrooms, so the answer is \(0\).
3. Otherwise, install air conditioners in the top \(M\) classrooms, and the answer is \(D[M]\) (0-indexed), the maximum among the remaining classrooms.

Why is this correct?

After sorting in descending order, \(D[0] \geq D[1] \geq \cdots \geq D[N-1]\). Since we can only reduce the deterioration level to \(0\) for \(M\) classrooms with \(M\) air conditioners, to minimize the maximum value among the remaining \(N - M\) classrooms, the best strategy is to eliminate the \(M\) largest values. The remaining maximum is then \(D[M]\).

Complexity

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

Implementation Notes

• Be careful about the sort direction (descending). If using ascending sort, you would reference \(D[N - M - 1]\) instead.

• The case \(M \geq N\) must be handled first; otherwise, accessing \(D[M]\) would result in an out-of-bounds array access.

  Source Code

N, M = map(int, input().split())
D = list(map(int, input().split()))
D.sort(reverse=True)
if M >= N:
    print(0)
else:
    print(D[M])

---

This editorial was generated by claude4.6opus-thinking.