Overview

Given each staff member’s assignment \(X_i\) with upper limit \(R_i\) and total sum \(M\), the problem asks to minimize \(\max(R_i - X_i)\) (the maximum difference from the upper limit). We reformulate this as a problem of distributing “deficiencies” and use binary search to find the minimum unfairness.

Analysis

1. Think about “deficiency” instead of “assignment”

The unfairness is the maximum value of \(R_i - X_i\). So let us define: - Deficiency \(D_i = R_i - X_i\) (\(0 \le D_i \le R_i\))

Then the condition \(X_1+\cdots+X_N=M\) can be transformed as follows.

Let \(S=\sum_{i=1}^N R_i\), then: [ \sum_{i=1}^N Xi = \sum{i=1}^N (R_i - Di) = S - \sum{i=1}^N Di = M ] Therefore: [ \sum{i=1}^N D_i = S - M = T ]

In other words, the problem is reformulated as:

• Each \(D_i\) satisfies \(0 \le D_i \le R_i\)
• The total \(\sum D_i = T\)
• Minimize the maximum \(\max D_i\)

Also, if \(M > S\), then even assigning everyone to their upper limit cannot reach \(M\) slots, so it is impossible → -1.

2. Directly constructing the optimal assignment is difficult

If we try to “directly construct \(X_i\) to minimize unfairness,” the adjustments become complex. With \(N\) up to \(2\times 10^5\) and values up to \(10^{18}\), brute-force search or simulation is not practical.

3. “Is unfairness \(d\) achievable?” is monotonic

Fix a candidate unfairness \(d\) (i.e., \(\max D_i \le d\)) and check whether “we can produce a total deficiency of \(T\).”

Each staff member \(i\)’s deficiency can be at most \(\min(d, R_i)\). Therefore, the maximum achievable total deficiency is: [ C(d) = \sum_{i=1}^N \min(d, R_i) ]

• If \(C(d) \ge T\), we can adjust each \(D_i\) to make the total \(T\) (since reducing deficiency is always possible) → achievable
• If \(C(d) < T\), no matter what we do, the total cannot reach \(T\) → not achievable

As \(d\) increases, \(\min(d, R_i)\) increases (or stays the same), so \(C(d)\) is monotonically non-decreasing. Therefore, “achievable/not achievable” is monotonic with respect to \(d\), and binary search can be applied.

Concrete Example

When \(R=[5,1,4],\ M=7\): \(S=10,\ T=S-M=3\). If \(d=1\), then \(C(1)=1+1+1=3\), so it is achievable (unfairness 1 can produce total deficiency 3). If \(d=0\), then \(C(0)=0\), so it is not achievable. Therefore the answer is 1.

Algorithm

1. Compute \(S=\sum R_i\).
2. If \(M > S\), output -1 and terminate.
3. Compute \(T = S - M\).
   • If \(T=0\) (i.e., \(M=S\)), no deficiency is needed, so unfairness is \(0\).
4. Use binary search to find the minimum \(d\).
   • Search range: \(0 \le d \le \max R_i\)
   • Check function: Compute \(C(d)=\sum \min(d, R_i)\) and determine achievable if \(C(d)\ge T\)
5. Output the minimum \(d\) found.

In the code, the binary search uses: - lo = an impossible value - hi = an achievable value

starting from lo=-1, hi=maxR, and hi becomes the answer.

Complexity

• Time complexity: \(O(N \log(\max R_i))\) (Each check is \(O(N)\), and binary search runs at most about 60 iterations)
• Space complexity: \(O(N)\) (To store the array \(R\))

Implementation Notes

• Impossibility check: When \(M > \sum R_i\), always output -1.

• Special handling for \(T=0\): Since deficiency is zero, the answer is always \(0\).

• Upper bound of binary search: \(\max R_i\) is sufficient (beyond that, \(\min(d,R_i)\) does not change).

• For the check computation \(\sum \min(d,R_i)\), early termination when the running total reaches \(T\) or above improves speed (the break in the code).

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, M = data[0], data[1]
    R = data[2:2+N]

    S = 0
    maxR = 0
    for r in R:
        S += r
        if r > maxR:
            maxR = r

    if M > S:
        print(-1)
        return

    T = S - M  # total deficit needed
    if T == 0:
        print(0)
        return

    lo, hi = -1, maxR  # lo: infeasible, hi: feasible
    while hi - lo > 1:
        mid = (lo + hi) // 2
        c = 0
        for r in R:
            c += mid if mid < r else r
            if c >= T:
                break
        if c >= T:
            hi = mid
        else:
            lo = mid

    print(hi)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.