Overview

This problem involves assigning a total of \(M\) shift slots to \(N\) staff members, while minimizing the maximum value of the “difference between each staff member’s upper limit \(R_i\) and their actual assignment \(X_i\).” Each staff member has the constraint \(0 \leq X_i \leq R_i\), and within this range, we need to adjust assignments so the total is exactly \(M\) while keeping the unfairness (maximum difference) as small as possible.

Analysis

1. Rephrasing Unfairness

Suppose we want to keep the unfairness at most \(D\). Then, for all \(i\), the following condition must hold: $\(R_i - X_i \leq D\)\( Rearranging for \)X_i\(: \)\(X_i \geq R_i - D\)\( Since we originally have the constraint \)0 \leq X_i \leq R_i\(, combining these gives the range of slots \)X_i\( to assign to each staff member: \)\(\max(0, R_i - D) \leq X_i \leq R_i\)$

2. Using Binary Search

Consider the decision problem: “Can we achieve unfairness at most \(D\)?” As \(D\) decreases, the condition becomes stricter, and as \(D\) increases, it becomes more relaxed. Therefore, we can apply binary search on the answer (the minimum unfairness).

To determine whether a given \(D\) is achievable, we check whether the sum of the minimum slots \(\max(0, R_i - D)\) assigned to each staff member is at most \(M\). (If the sum is at most \(M\), we can appropriately add the remaining \(M - \sum \max(0, R_i - D)\) slots to staff members without exceeding their \(R_i\), making the total exactly \(M\). However, if the total upper limit \(\sum R_i\) is less than \(M\), it is impossible.)

3. Speeding Up the Decision

If we compute \(\max(0, R_i - D)\) for all \(N\) staff members at each decision step, the overall complexity is \(O(N \log (\max R))\), which may be fast enough depending on the constraints, but we can compute it more efficiently. If we sort \(R_i\) in ascending order, there exists a boundary \(k\) such that: - When \(R_i \leq D\): \(\max(0, R_i - D) = 0\) - When \(R_i > D\): \(\max(0, R_i - D) = R_i - D\)

This boundary \(k\) can be found using binary search (bisect_right), and the sum of the latter part can be computed in \(O(1)\) using a prefix sum.

Algorithm

1. Initial Check: If the total of all upper limits \(\sum R_i\) is less than \(M\), it is impossible to reach a total of \(M\) regardless of assignment, so output -1.
2. Preprocessing: Sort \(R\) in ascending order and compute the prefix sum.
3. Binary Search:
   • Search range: low = 0, high = max(R)
   • Decision function check(D):
     • Find the smallest index \(k\) such that \(R_i > D\).
     • Compute the sum from \(R_k\) to \(R_{N-1}\), then subtract \((N-k) \times D\).
     • Return True if that value is at most \(M\), otherwise False.
4. Output: Output the minimum \(D\) for which the decision returns True.

Complexity

• Time Complexity: \(O(N \log N + \log (\max R) \cdot \log N)\)
  • Sorting takes \(O(N \log N)\).
  • The number of binary search iterations is \(O(\log (\max R))\) (approximately 60), and each decision takes \(O(\log N)\), so it is sufficiently fast.
• Space Complexity: \(O(N)\)
  • Required to store the array \(R\) and the prefix sum array.

Implementation Notes

• Since \(M\) and \(R_i\) can be as large as \(10^{18}\), care must be taken with overflow when computing sums (in Python, this is not an issue since integers are automatically handled as arbitrary-precision).

• Since \(N\) can be as large as \(2 \times 10^5\), fast I/O using sys.stdin.read().split() is recommended.

  Source Code

import sys
from bisect import bisect_right

def solve():
    # Fast I/O: Read all input at once and split into tokens
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # N: Number of staff members
    # M: Total number of shifts to be assigned
    N = int(input_data[0])
    M = int(input_data[1])
    
    # R: List of upper limit shifts for each staff member
    # R_i can be up to 10^18, and N up to 2*10^5.
    R = list(map(int, input_data[2:2+N]))
    
    # Sort R to allow for efficient sum calculation using prefix sums and binary search
    R.sort()
    
    # Precompute prefix sums to calculate the sum of any range in O(1)
    prefix_sum = [0] * (N + 1)
    for i in range(N):
        prefix_sum[i+1] = prefix_sum[i] + R[i]
        
    # The total capacity of all staff members must be at least M
    total_capacity = prefix_sum[N]
    if total_capacity < M:
        print("-1")
        return
        
    # Function to calculate the minimum total shifts assigned given a maximum unfairness D.
    # Unfairness D = max(R_i - X_i) implies X_i >= R_i - D for each staff member.
    # Since 0 <= X_i <= R_i, we have max(0, R_i - D) <= X_i <= R_i.
    # To minimize the sum of X_i, we take X_i = max(0, R_i - D).
    def get_min_sum(D):
        # Find the index k such that R[k] > D.
        # For i < k, R[i] - D <= 0, so max(0, R[i] - D) = 0.
        # For i >= k, R[i] - D > 0, so max(0, R[i] - D) = R[i] - D.
        k = bisect_right(R, D)
        count = N - k
        sum_R_k_to_N = prefix_sum[N] - prefix_sum[k]
        # Sum of (R_i - D) for i from k to N-1
        return sum_R_k_to_N - count * D

    # Binary search for the minimum unfairness D in the range [0, max(R)]
    low = 0
    high = R[-1]
    ans = high
    
    while low <= high:
        mid = (low + high) // 2
        # If the minimum required sum for unfairness 'mid' is <= M,
        # it is possible to achieve an unfairness of 'mid' by increasing some X_i.
        if get_min_sum(mid) <= M:
            ans = mid
            high = mid - 1
        else:
            low = mid + 1
            
    print(ans)

if __name__ == "__main__":
    solve()

This editorial was generated by gemini-3-flash-thinking.