Overview

When assigning \(M\) shifts to \(N\) staff members, find an assignment that minimizes the unfairness \(\max (R_i - X_i)\) without exceeding each staff member’s upper limit \(R_i\). If no valid assignment exists, output -1.

Analysis

The goal of this problem is to minimize the unfairness. Unfairness is defined as the maximum value of “how many fewer shifts each staff member is assigned compared to their upper limit,” and we want to minimize this so that no one is extremely disadvantaged.

Issues with a Naive Approach

A simple idea would be to assign shifts equally to each staff member, but since the upper limits \(R_i\) differ between people, a simple equal distribution is not optimal. Additionally, the assignments must sum to exactly \(M\), which requires careful handling.

Solution Idea

If we can fix the unfairness and determine whether \(M\) shifts can be assigned under that unfairness, we can use binary search. Specifically, under the condition “unfairness is at most \(d\),” each staff member must be assigned at least \(X_i = \max(0, R_i - d)\) shifts. If the total of these values is at most \(M\), we can further adjust to reach exactly \(M\), so it works.

Conversely, for unfairness \(d\), if \(\sum \max(0, R_i - d) > M\), then that \(d\) results in over-assignment, meaning we need to make the unfairness even smaller.

In this way, we can find the minimum unfairness using binary search.

Algorithm

1. First, if the total when assigning everyone their upper limit \(\sum R_i\) is less than \(M\), no valid assignment exists → output -1.
2. Use binary search to find the minimum unfairness \(d\).
   • Search range: \(d = 0\) to \(\max(R_i)\)
   • For each \(d\), compute \(\sum \max(0, R_i - d)\) and check whether it is at most \(M\).
   • Find the smallest \(d\) that satisfies the condition.

Complexity

• Time complexity: \(O(N \log(\max(R_i)))\)
• Space complexity: \(O(1)\) (excluding input)

※ Each step of the binary search requires scanning the entire array, which is \(O(N)\), and the number of search iterations is \(O(\log(\max(R_i)))\).

Implementation Notes

• Ensure the binary search termination condition left <= right is maintained.

• Don’t forget the computation of max(0, R[i] - d).

• Since the input can be very large, it is recommended to use sys.stdin.read for fast input reading.

• Since the total can become very large, Python’s integer type handles this safely.

  Source Code

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    R = list(map(int, data[2:]))
    
    # 総和チェック: 割り当て可能か
    total_max = sum(R)
    if M > total_max:
        print(-1)
        return
    
    # 割り当て不能なケース（Mが負でもないかチェック）
    if M < 0:
        print(-1)
        return

    # 不公平度を最小化するには、各R[i] - X[i] の最大値を最小にする
    # つまり、X[i] = max(0, R[i] - d) のように設定し、sum(X) == M となるような最小のdを探す
    
    # 二分探索でdの最小値を求める
    def is_possible(d):
        # 各スタッフに割り当て可能な最大は R[i]
        # 不公平度がd以下にするには、X[i] >= R[i] - d
        # かつ X[i] >= 0, X[i] <= R[i]
        # よって X[i] = max(0, R[i] - d) から R[i] の間で調整可能
        assigned = 0
        for r in R:
            x = max(0, r - d)
            assigned += x
        return assigned <= M  # 割り当てすぎていないか

    # dの探索範囲: 0 から max(R)
    left = 0
    right = max(R) if R else 0
    answer = -1

    while left <= right:
        mid = (left + right) // 2
        # d=midで達成できる最小割り当てを試す
        min_assigned = sum(max(0, r - mid) for r in R)
        if min_assigned <= M:
            answer = mid
            right = mid - 1
        else:
            left = mid + 1

    print(answer)

if __name__ == "__main__":
    main()

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