Overview

This problem asks us to assign a total of \(M\) shifts to \(N\) staff members, minimizing the maximum value of “the difference between each staff member’s upper limit and their actual assignment” (unfairness). It can be solved efficiently by performing binary search on the value of unfairness.

Analysis

Key Insight: Binary search on the answer

Let the unfairness be \(d\). For each staff member \(i\), the requirement is \(R_i - X_i \leq d\), which means \(X_i \geq R_i - d\). Combined with the constraint \(0 \leq X_i \leq R_i\), the feasible assignment range for each staff member is:

\[\max(0, R_i - d) \leq X_i \leq R_i\]

To achieve the total \(\sum X_i = M\), it is possible if and only if the minimum total \(\sum \max(0, R_i - d)\) is at most \(M\) and the maximum total \(\sum R_i = S\) is at least \(M\).

Since \(M \leq S\) is checked beforehand (output -1 if violated), the key observation is that if \(d\) is large enough, \(\sum \max(0, R_i - d) \leq M\) holds — this has monotonicity. In other words, the larger \(d\) is, the easier the condition becomes, so we can find the minimum \(d\) via binary search.

Problem with the Naive Approach

When \(d\) is fixed, naively computing \(\sum \max(0, R_i - d)\) takes \(O(N)\), resulting in \(O(N \log(\max R_i))\) combined with binary search. This is fast enough, but sorting the array and using binary search + prefix sums to speed up the computation of \(\sum \max(0, R_i - d)\) makes the approach even cleaner.

Algorithm

1. Impossibility check: If \(M > \sum R_i\), output -1 and terminate.
2. Precomputation with sorting and prefix sums: Sort \(R\) in ascending order and build a prefix sum array \(\text{prefix}\).
3. Binary search on the answer \(d\): The range of \(d\) is \([0, \max(R_i)]\).
   • For a fixed \(d\), only staff members with \(R_i > d\) have a lower bound of \(R_i - d\). Use binary search on the sorted \(R\) to find the first index where \(R_i > d\).
   • Compute \(\sum (R_i - d)\) for those staff members in \(O(\log N)\) using the prefix sum.
   • If this value is at most \(M\), then \(d\) is large enough (try making \(d\) smaller); otherwise, make \(d\) larger.
4. The final value of \(d\) found is the answer.

Concrete Example

For \(N = 3, M = 7, R = [5, 3, 4]\), we have \(S = 12\).

• When \(d = 2\): the lower bound sum is \(\max(0, 5-2) + \max(0, 3-2) + \max(0, 4-2) = 3 + 1 + 2 = 6 \leq 7\). OK.
• When \(d = 1\): the lower bound sum is \(4 + 2 + 3 = 9 > 7\). NG.

Therefore the answer is \(d = 2\). (For example, not \(X = [5, 0, 2]\) but something like \(X = [3, 1, 3]\) is achievable.)

Complexity

• Time complexity: \(O(N \log N + N \log(\max R_i))\)
  • \(O(N \log N)\) for sorting, \(O(\log N)\) for the inner binary search at each step, and \(O(\log(\max R_i))\) steps for the outer binary search.
• Space complexity: \(O(N)\) (prefix sum array)

Implementation Notes

• Since \(M\) and \(R_i\) can be as large as \(10^{18}\), overflow must be handled carefully (in Python, arbitrary-precision integers make this a non-issue).

• The key technique for computing \(\sum \max(0, R_i - d)\) is to use binary search on the sorted array to identify the range where \(R_i > d\), then use prefix sums to compute the result in \(O(\log N)\).

• When \(M = 0\), all staff members are assigned \(0\) shifts, and the unfairness is \(\max(R_i)\). This is naturally handled by the binary search as well.

  Source Code

import sys

def solve():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    M = int(input_data[1])
    R = [int(input_data[i + 2]) for i in range(N)]
    
    S = sum(R)
    
    # If M > S, impossible since we can't assign more than sum of R_i
    if M > S:
        print(-1)
        return
    
    # If M == S, everyone gets their max, unfairness = 0
    # We need to minimize max(R_i - X_i) where sum(X_i) = M, 0 <= X_i <= R_i
    
    # Binary search on the answer d (unfairness)
    # For a given d, we need: R_i - X_i <= d for all i, i.e., X_i >= R_i - d
    # Also X_i <= R_i and X_i >= 0
    # So X_i >= max(0, R_i - d) and X_i <= R_i
    # 
    # The minimum total assignment = sum(max(0, R_i - d))
    # The maximum total assignment = sum(R_i) = S
    # 
    # We need min_total <= M <= max_total = S
    # Since M <= S is already guaranteed, we just need sum(max(0, R_i - d)) <= M
    
    # We need to find the smallest d >= 0 such that sum(max(0, R_i - d)) <= M
    
    # Sort R to efficiently compute sum(max(0, R_i - d))
    R.sort()
    
    # Prefix sums
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i + 1] = prefix[i] + R[i]
    
    def min_total(d):
        # sum of max(0, R_i - d) for all i
        # R is sorted. Find first index where R[idx] > d
        # For R[i] <= d: contribution is 0
        # For R[i] > d: contribution is R[i] - d
        lo, hi = 0, N
        while lo < hi:
            mid = (lo + hi) // 2
            if R[mid] > d:
                hi = mid
            else:
                lo = mid + 1
        # lo = first index where R[idx] > d
        # sum of (R[i] - d) for i in [lo, N-1]
        count = N - lo
        s = prefix[N] - prefix[lo]
        return s - d * count
    
    # Binary search: find smallest d >= 0 such that min_total(d) <= M
    # d ranges from 0 to max(R) (or could be 0 if M >= S which gives d=0... well M==S gives d=0)
    
    # If d = max(R), min_total = 0 <= M always (since M >= 0)
    # If d = 0, min_total = S. We need S <= M, which means M = S (since M <= S). 
    
    # Check if M == 0: then X_i = 0 for all i, unfairness = max(R_i)
    # Actually that's handled by the binary search.
    
    # Edge: if M < 0 shouldn't happen given constraints
    
    lo_d = 0
    hi_d = max(R) if N > 0 else 0
    
    # Check: at d = hi_d, min_total should be <= M
    # min_total(max(R)) = sum(max(0, R_i - max(R))) = 0 <= M. Good.
    
    while lo_d < hi_d:
        mid_d = (lo_d + hi_d) // 2
        if min_total(mid_d) <= M:
            hi_d = mid_d
        else:
            lo_d = mid_d + 1
    
    print(lo_d)

solve()

---

This editorial was generated by claude4.6opus-thinking.