Overview

Given the deterioration levels \(D_i\) of \(N\) classrooms, the problem asks to install at most \(M\) air conditioners (setting the deterioration level of installed classrooms to \(0\)) to minimize the maximum deterioration level across all classrooms.

Analysis

The goal of this problem is to “make the overall maximum value as small as possible.”

When a new air conditioner is installed in a classroom, that classroom’s deterioration level becomes \(0\). To reduce the overall maximum deterioration level, it is most efficient to prioritize installing air conditioners in classrooms with the highest deterioration levels (largest values).

For example, consider 3 classrooms with deterioration levels \([10, 50, 100]\) and 1 air conditioner available. - If installed in the classroom with deterioration \(10\): the levels become \([0, 50, 100]\), and the maximum is \(100\). - If installed in the classroom with deterioration \(100\): the levels become \([10, 50, 0]\), and the maximum is \(50\).

In this way, by selecting the \(M\) largest values and replacing them with \(0\), the maximum among the remaining values becomes the minimum possible maximum value achievable.

Algorithm

1. Sort the list of classroom deterioration levels \(D\) in ascending order (smallest first).
2. If the number of air conditioners \(M\) is greater than or equal to the number of classrooms \(N\), air conditioners can be installed in all classrooms, so the maximum is \(0\).
3. If the number of air conditioners \(M\) is less than \(N\), install air conditioners in the \(M\) classrooms with the highest deterioration levels.
   • In the sorted list \(D\), the last \(M\) elements become \(0\).
   • The maximum among the remaining elements is the \(N-M\)-th element of the sorted list (index \(N-M-1\) in 0-indexed).
4. Output that value as the answer.

Complexity

• Time complexity: \(O(N \log N)\)
  • Reading the data takes \(O(N)\), and sorting the list takes \(O(N \log N)\). The subsequent value lookup is \(O(1)\).
• Space complexity: \(O(N)\)
  • Memory is needed for the list holding the \(N\) deterioration levels.

Implementation Notes

• Since the values of \(N\) and \(M\) can be as large as \(2 \times 10^5\), in Python it is advisable to use sys.stdin.read().split() or similar methods for fast input processing.

• Be careful not to make mistakes with index specification after sorting. For example, when \(N=5, M=2\), in the sorted list \(D = [D_0, D_1, D_2, D_3, D_4]\), the 2 largest values (\(D_3, D_4\)) are set to \(0\), so the remaining maximum is \(D_{5-2-1} = D_2\).

  Source Code

import sys

def solve():
    # 入力をすべて読み込み、スペースや改行で分割する
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 教室の数, M: 新しいエアコンの台数
    n = int(input_data[0])
    m = int(input_data[1])
    
    # D: 各教室の老朽度
    d = list(map(int, input_data[2:]))
    
    # 老朽度を昇順（小さい順）にソートする
    d.sort()
    
    # 老朽度の最大値を最小化するためには、老朽度が高い教室から優先的に
    # 新しいエアコンを設置するのが最適である。
    # 最大M台のエアコンを設置できるため、老朽度が大きい方からM個を0に置き換える。
    
    if m >= n:
        # エアコンの台数が教室の数以上であれば、すべての教室の老朽度を0にできる
        print(0)
    else:
        # エアコンをM台設置したとき、残った教室の中で最大の老朽度は、
        # ソート後のリストにおいて後ろからM個を除いた中での最大値、
        # すなわちインデックス N-M-1 の要素となる。
        print(d[n - m - 1])

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-thinking.