\(A\) の並びは関係ないので、\(A\) をソートして考えます。

お菓子は \(N\) 人の間で受け渡されるので、総和 \(\displaystyle S=\sum_i A_i\) は変わりません。この条件下で最大値と最小値の差が \(1\) 以下、という条件を考えると実は \(\displaystyle B_i=\left\lfloor\frac{S+i}N \right\rfloor\) (0-indexed) として最終的なお菓子の個数は \(B_0,B_1,\ldots,B_{N-1}\) となります。

はじめ持っているお菓子が少ない人には最終的に持っているお菓子の数も少なくして良いので、求める答えは \(\displaystyle \sum_i \max(0,B_i-A_i)\) となります。

以上を適切に実装することでこの問題に正答することができます。計算量は \(O(N\log N)\) です。

実装例(Python3)

n = int(input())
a = sorted(map(int, input().split()))
s = sum(a)
print(sum(max((s + i) // n - a[i], 0) for i in range(n)))