Overview

This problem asks for the number of operations needed to equalize the candies held by \(N\) children until “the difference between the maximum and minimum is at most \(1\).” We directly calculate the final state and determine the number of operations required to reach it.

Analysis

What does the final state look like?

The total number of candies \(S = \sum A_i\) does not change through the operations. In the final state, the difference between any two children is at most \(1\), so letting \(q = \lfloor S/N \rfloor\) and \(r = S \bmod N\):

• \(N - r\) children hold \(q\) candies
• \(r\) children hold \(q + 1\) candies

This is the state that will always be reached.

How do we count the number of operations?

In one operation, “the child with the most loses 1 candy, and the child with the least gains 1 candy,” so the number of operations equals the total number of candies collected from children who have more than their target (the collected amount is directly given to the children who are short).

Why naive simulation doesn’t work

Since \(A_i\) can be up to \(10^9\), naively simulating the operation of moving one candy at a time would result in an enormous number of operations (worst case around \(O(N \times 10^9)\)), causing TLE.

Considering the optimal assignment

By assigning sorted target values to the sorted array \(A\), we can directly calculate “how far each child deviates from the target.” Specifically, sort \(A\) in ascending order, assign target \(q\) to the first \(N - r\) children, and assign target \(q + 1\) to the remaining \(r\) children.

Concrete example: \(N = 4\), \(A = [1, 8, 3, 4]\) → \(S = 16\), \(q = 4\), \(r = 0\)

• After sorting: \([1, 3, 4, 8]\)
• Targets: \([4, 4, 4, 4]\)
• Differences: \([-3, -1, 0, +4]\)
• Sum of excesses: \(4\) → The answer is \(4\)

Algorithm

1. Compute \(S = \sum A_i\), then calculate \(q = \lfloor S/N \rfloor\) and \(r = S \bmod N\).
2. Sort \(A\) in ascending order.
3. Assign target \(q\) to the first \(N - r\) elements of the sorted \(A\), and target \(q + 1\) to the remaining \(r\) elements.
4. Compute the sum of the parts where \(A_i\) exceeds the target: \(\sum \max(A_i - \text{target}_i, 0)\). This is the answer.

Complexity

• Time complexity: \(O(N \log N)\) (sorting is the bottleneck)
• Space complexity: \(O(N)\) (storing the array)

Implementation Notes

• Since \(A_i\) can be up to \(10^9\) and \(N\) can be up to \(5 \times 10^5\), the answer can be very large. Use 64-bit integers (Python handles this automatically).

• You only need to sum up the excess over the target (since the total excess equals the total deficit, computing either one is sufficient).

• Using sys.stdin.buffer.read() enables fast processing of large inputs.

  Source Code

import sys

def solve():
    data = sys.stdin.buffer.read().split()
    N = int(data[0])
    A = [int(data[i + 1]) for i in range(N)]
    
    S = sum(A)
    q, r = divmod(S, N)
    
    # Sort A in non-decreasing order
    A.sort()
    
    # Sorted targets: first (N - r) children get q, last r children get q + 1
    ans = 0
    for i in range(N):
        if i < N - r:
            target = q
        else:
            target = q + 1
        if A[i] > target:
            ans += A[i] - target
    
    print(ans)

solve()

---

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