概要

\(N\) 個の教室のうち最大 \(M\) 個にエアコンを設置して老朽度を \(0\) にできるとき、残りの教室の老朽度の最大値を最小化する問題です。老朽度が大きい教室から優先的にエアコンを設置するのが最適です。

考察

重要な気づき：貪欲法が最適

老朽度の最大値を最小化したいので、老朽度が大きい教室ほど優先してエアコンを設置すべきです。

具体例で考えてみましょう。\(N = 5, M = 2\) で老朽度が \([3, 7, 1, 9, 5]\) の場合：

• 老朽度を降順にソートすると \([9, 7, 5, 3, 1]\)
• エアコン \(2\) 台を老朽度が大きい上位 \(2\) 教室（老朽度 \(9\) と \(7\)）に設置
• 設置後の老朽度は \([0, 0, 5, 3, 1]\)
• 最大値は \(5\)

もし別の教室に設置したら、\(9\) や \(7\) が残ってしまい、最大値がより大きくなります。

答えはソート後の \(M\) 番目

老朽度を降順にソートしたとき、上位 \(M\) 個の教室にエアコンを設置すれば、残る教室のうち最大の老朽度は降順で \(M+1\) 番目（0-indexed で \(D[M]\)）の値になります。

特殊ケース

\(M \geq N\) の場合、全教室にエアコンを設置できるため、答えは \(0\) です。

アルゴリズム

1. 老朽度の配列 \(D\) を降順にソートする。
2. \(M \geq N\) ならば、全教室にエアコンを配置できるので答えは \(0\)。
3. そうでなければ、上位 \(M\) 個にエアコンを設置し、残った中で最大の \(D[M]\)（0-indexed）が答え。

なぜこれで正しいか？

降順ソート後、\(D[0] \geq D[1] \geq \cdots \geq D[N-1]\) です。\(M\) 台のエアコンで老朽度を \(0\) にできる教室は \(M\) 個だけなので、残りの \(N - M\) 個の中の最大値を最小にするには、最も大きい \(M\) 個を消すのが最善です。すると残る最大値は \(D[M]\) です。

計算量

• 時間計算量: \(O(N \log N)\)（ソートが支配的）
• 空間計算量: \(O(N)\)（配列の格納）

実装のポイント

• ソートの向き（降順）に注意。昇順ソートの場合は \(D[N - M - 1]\) を参照することになります。

• \(M \geq N\) の場合を先に処理しないと、\(D[M]\) で配列の範囲外アクセスが発生するので注意が必要です。

  ソースコード

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

---

この解説は claude4.6opus-thinking によって生成されました。