Overview

Given a deterioration array \(D\), you can select at most \(M\) classrooms and set their deterioration to \(0\). Find the value that minimizes the “maximum deterioration” after installation.

Analysis

Since installing a new air conditioner always sets that classroom’s deterioration to \(0\), the only question is “which classrooms to set to \(0\).”

The key observation is as follows:

• To reduce the maximum deterioration, it is optimal to prioritize setting the largest deterioration values to \(0\).
  If you leave large values and set small values to \(0\), the maximum remains at the large value and does not decrease.

For example, when \(D=[8,5,3,1],\ M=1\): - Setting \(8\) to \(0\) leaves \([5,3,1,0]\) with a maximum of \(5\) - Setting \(1\) to \(0\) leaves \([8,5,3,0]\) with a maximum of \(8\) (no improvement)

Therefore, to minimize the maximum value, the best strategy is to “set the \(M\) largest deterioration values to \(0\).”

A brute-force approach of trying all possible classroom selections would involve \({N \choose M}\) combinations, which is far too slow for \(N \le 2\times 10^5\) (TLE).

With this observation, the answer is actually determined by sorting alone.

Algorithm

1. Sort the array \(D\) in descending order (largest first).
2. If \(M \ge N\), all classrooms can be set to \(0\), so the answer is \(0\).
3. Otherwise, after setting the top \(M\) values to \(0\), the remaining maximum is the “\((M+1)\)-th largest value.”
   Using 0-indexed notation with \(D\) as the descending sorted array, the answer is \(D[M]\).

(When sorted in descending order, indices \(0 \sim M-1\) are the installation targets, and the head of the remaining portion \(D[M]\) becomes the maximum.)

Complexity

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

Implementation Notes

• After sorting in descending order, output \(D[M]\) (be careful with 0-indexing).

• When \(M = N\), accessing \(D[M]\) is out of bounds, so check \(M \ge N\) first and output \(0\).

• Since the input size can be large, using sys.stdin.buffer.read() is a safe way to speed up input.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, M = data[0], data[1]
    D = data[2:]
    D.sort(reverse=True)
    if M >= N:
        print(0)
    else:
        print(D[M])

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.