Overview

Given the deterioration levels of \(N\) classrooms, you can change at most \(M\) of them to \(0\). The problem asks to minimize the maximum deterioration level after the changes.

Analysis

In this problem, you can install at most \(M\) new air conditioners, each of which reduces a classroom’s deterioration level to \(0\). The goal is to minimize the “maximum deterioration level across all classrooms.”

A naive approach might be to “set the \(M\) largest deterioration levels to \(0\).” However, this is not always optimal. For example, if the deterioration levels are [100, 90, 10] and \(M=1\), we could achieve a maximum of \(90\), but simply setting the largest to \(0\) would leave the maximum at \(100\).

Here is the key observation: - Consider the decision problem: “Can we make the final maximum deterioration level at most \(x\)?” This can be solved efficiently. - For classrooms with deterioration levels greater than \(x\), we must install a new air conditioner. - If the number of such classrooms is at most \(M\), it is achievable.

For such “minimize the maximum” problems, binary search is extremely effective. The search range is from \(0\) to \(\max(D_i)\), and we simply check whether a given value \(x\) satisfies the condition.

Algorithm

1. Sort the deterioration level list \(D\) in descending order (largest first).
2. Use binary search to find the minimum possible value of the “final maximum deterioration level.”
3. At each step, determine whether a given value \(x\) is “achievable.”
   • Count the number of classrooms where \(D_i > x\), and if this count is at most \(M\), it is achievable.
4. Output the minimum achievable maximum value found by binary search.

Example

Input:

5 2
8 2 10 1 5

Processing flow: - After sorting: [10, 8, 5, 2, 1] - Try candidate maximum values via binary search. - For example, to achieve a maximum of 5, we need to install air conditioners in the 2 classrooms with deterioration levels 10 and 8 → required units: 2 → \(M=2\), so it’s OK.

Complexity

• Time complexity: \(O(N \log N + N \log(\max(D)))\)
  • \(O(N \log N)\) for sorting, and at each binary search step we scan up to \(N\) elements, with \(\log(\max(D))\) steps required.
• Space complexity: \(O(1)\) (excluding input data)

Implementation Notes

• When using binary search, carefully handle the updates of left, right, and mid.

• In the decision function is_achievable(), use the sorted array to efficiently compute the required number of air conditioners.

• sys.stdin.read is used for fast input reading.

  Source Code

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    D = list(map(int, data[2:]))

    # 老朽度を降順にソートする
    D.sort(reverse=True)

    # 最大値を最小化する → 二分探索
    def is_achievable(max_val):
        # 老朽度がmax_valを超える教室には新しいエアコンが必要
        needed = 0
        for d in D:
            if d > max_val:
                needed += 1
            else:
                break
        return needed <= M

    # 二分探索の範囲
    left = 0
    right = max(D)
    answer = right

    while left <= right:
        mid = (left + right) // 2
        if is_achievable(mid):
            answer = mid
            right = mid - 1
        else:
            left = mid + 1

    print(answer)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.