概要

各操作は「多い人から少ない人へ 1 個移す」だけなので、最終状態は全員が \(\lfloor \frac{S}{N} \rfloor\) または \(\lceil \frac{S}{N} \rceil\)（\(S=\sum A_i\)）になります。
この最終形にそろえるために「不足している個数の合計」を求めれば、それが操作回数になります。

考察

重要な観察は次の2つです。

1. 最終的な個数は2種類だけ
   総和 \(S\) は保存されるので、全員同じにはできない場合でも差は高々1までしか許されません。
   よって最終的に
   • \(q=\left\lfloor \frac{S}{N} \right\rfloor\)
   • \(q+1\)

のどちらかになります。
また \(S = qN + r\)（\(0 \le r < N\)）より、\(q+1\) を持つ子はちょうど \(r\) 人です。

1. 操作回数 = 不足分の合計
   1回の操作で「不足している側」はちょうど1個埋まり、「余っている側」は1個減ります。
   したがって、最終目標に対する不足分の総和を数えれば、それが必要操作回数そのものです。

---

素朴にシミュレーション（毎回 max/min を探して 1 個移す）すると、操作回数が非常に多くなりうるため間に合いません。
\(A_i\) は最大 \(10^9\) なので、1個ずつ動かす実装は不可能です。

ではどう不足分を正しく数えるか？
ここで ソート が効きます。

• 昇順に並べると、小さい値の人から順に目標値を割り当てるのが自然
• 最終的に小さい方 \(N-r\) 人は \(q\)
• 大きい方 \(r\) 人は \(q+1\)

この対応で各人の不足分だけ足せばよいです（超過分は数えない）。
不足分総和と超過分総和は一致するため、どちらを数えても同じ答えになります。

アルゴリズム

1. \(S=\sum A_i\) を計算
2. \(q, r = \mathrm{divmod}(S, N)\) を求める
   
   • 目標は \(q\) が \(N-r\) 人、\(q+1\) が \(r\) 人
3. \(A\) を昇順ソート
4. 前半 \(N-r\) 人について、\(A_i<q\) なら \(q-A_i\) を加算
5. 後半 \(r\) 人について、\(A_i<q+1\) なら \((q+1)-A_i\) を加算
6. 合計を出力

この合計が操作回数。

計算量

• 時間計算量: \(O(N \log N)\)（ソート）
• 空間計算量: \(O(N)\)（配列保持）

実装のポイント

• 答えは大きくなる可能性があるので、64bit整数で扱う（Pythonなら通常の int でOK）。

• divmod(s, n) を使うと \(q, r\) を簡潔に求められます。

• 不足分のみを足す（if A[i] < target）ことで実装がシンプルになります。

• \(N=1\) でもこの式で自然に 0 回になります。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    n = int(input().strip())
    A = list(map(int, input().split()))
    
    s = sum(A)
    q, r = divmod(s, n)  # final values are q or q+1, with exactly r children having q+1
    
    A.sort()
    
    # In sorted target arrangement:
    # first n-r elements -> q
    # last r elements -> q+1
    need = 0  # total candies needed by those below target
    split = n - r
    
    for i in range(split):
        if A[i] < q:
            need += q - A[i]
    
    high = q + 1
    for i in range(split, n):
        if A[i] < high:
            need += high - A[i]
    
    print(need)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.3-codex によって生成されました。