Overview

In the end, everyone’s number of candies can only be either the floor of the average \(q=\left\lfloor \frac{S}{N} \right\rfloor\) or \(q+1\).
Therefore, by cleverly deciding which children end up with \(q\) or \(q+1\) candies and counting the total shortfall, we can determine the number of operations.

Analysis

First, let the total number of candies be \(S=\sum A_i\).

1. What does the final state look like?

When operations are complete, “the difference between any two people is at most \(1\).”
At this point, if the minimum value is \(m\), then everyone’s count is either \(m\) or \(m+1\).

Meanwhile, since the average is \(\frac{S}{N}\), let: - \(q=\left\lfloor \frac{S}{N} \right\rfloor\) - \(r=S \bmod N\)

Then the final state must be:

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

This is because the total becomes: [ q(N-r)+(q+1)r=qN+r=S ]

In other words, the multiset of final counts (the collection ignoring order) is uniquely determined as: [ [q,q,\dots,q,q+1,\dots,q+1] ]

---

2. The number of operations equals the “total shortfall”

Given a chosen final state, let \(T_i\) be the target number of candies for child \(i\).

• If \(A_i < T_i\), that child needs to receive \(T_i-A_i\) candies
• If \(A_i > T_i\), that child has a surplus

Since each operation increases only one person’s count by 1, the required number of operations is at least: [ \sum \max(0, T_i-A_i) ]

Conversely, since the total does not change, the sum of shortfalls equals the sum of surpluses.
Therefore, by transferring 1 candy at a time from children with surplus to children with shortfall, we can achieve exactly this number of operations.

Hence, number of operations = total shortfall.

---

3. Which children should end up with \(q+1\) candies?

This is the key part.

There are \(r\) children who will end up with \(q+1\) candies, but which ones should they be for an optimal result?

Intuitively, it is better to assign \(q+1\) to children who originally have more candies.
If we assign \(q+1\) to children with fewer candies, we would need extra replenishment.

So we sort \(A\) in ascending order.
Then the optimal assignment is:

• The \(N-r\) children with the smallest values → target \(q\)
• The \(r\) children with the largest values → target \(q+1\)

In other words, if we let \(a\) be the sorted array, we simply match it with the target array in the same order: [ [q,\dots,q,q+1,\dots,q+1] ]

---

4. Why simulation doesn’t work

If we naively simulate “take the maximum and minimum each time and move 1 candy,” even using a priority queue, each step costs \(O(\log N)\).

However, the number of operations itself can be extremely large.
For example, if \(N=2, A=[0,10^9]\), the answer is \(5\times 10^8\) operations.

Because of this, simulating one operation at a time is far too slow.
We need to directly consider the final state and compute the total number of moves all at once.

Algorithm

1. Compute \(S=\sum A_i\)
2. Calculate \(q, r = \mathrm{divmod}(S, N)\)
3. Sort the array \(A\) in ascending order
4. Set the target for the first \(N-r\) elements (after sorting) to \(q\), and the last \(r\) elements to \(q+1\)
5. Add up only the shortfalls for each element: [ \text{ans}=\sum_{i=0}^{N-r-1}\max(0,q-ai) +\sum{i=N-r}^{N-1}\max(0,q+1-a_i) ]
6. Output ans

Concrete Example

For example, suppose: [ A=[0,1,8,9],\ N=4 ]

• Total \(S=18\)
• \(q=\lfloor 18/4 \rfloor=4\)
• \(r=2\)

The final state is: [ [4,4,5,5] ]

The sorted \(A\) is as-is: [ [0,1,8,9] ] So the shortfalls are:

• \(0 \to 4\): shortfall of 4
• \(1 \to 4\): shortfall of 3
• \(8 \to 5\): no shortfall
• \(9 \to 5\): no shortfall

Total: [ 4+3=7 ] Therefore the answer is 7.

Complexity

• Time complexity: \(O(N \log N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• When r = 0, everyone’s target is \(q\) candies. In the code, setting border = n - r handles this naturally.

• The answer can be large, so in C++ you need long long. In Python, this is handled automatically.

• Since the input can be large, in Python using fast input such as sys.stdin.buffer.read() is effective.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    n = data[0]
    a = data[1:1 + n]

    s = sum(a)
    q, r = divmod(s, n)

    a.sort()

    ans = 0
    border = n - r

    for i in range(border):
        if a[i] < q:
            ans += q - a[i]

    qp1 = q + 1
    for i in range(border, n):
        if a[i] < qp1:
            ans += qp1 - a[i]

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.