概要

最終的に全員のお菓子の個数は、平均値の切り捨て \(q=\left\lfloor \frac{S}{N} \right\rfloor\) または \(q+1\) にしかなりません。
そこで、どの子が最終的に \(q\) 個・\(q+1\) 個になるかをうまく決め、足りない個数の合計を数えれば操作回数が求まります。

考察

まず、お菓子の総数を \(S=\sum A_i\) とします。

1. 最終状態はどんな形か

操作終了時には「どの \(2\) 人の差も \(1\) 以下」です。
このとき、最小値を \(m\) とすると、全員の個数は \(m\) または \(m+1\) です。

一方、平均は \(\frac{S}{N}\) なので、 - \(q=\left\lfloor \frac{S}{N} \right\rfloor\) - \(r=S \bmod N\)

とおくと、最終状態は必ず

• \(q\) 個の子が \(N-r\) 人
• \(q+1\) 個の子が \(r\) 人

になります。
なぜなら、合計が [ q(N-r)+(q+1)r=qN+r=S ] になるからです。

つまり、最終的な個数の multiset（並び替えを無視した集合）は [ [q,q,\dots,q,q+1,\dots,q+1] ] で一意に決まります。

---

2. 操作回数は「足りない分の合計」

ある最終状態を決めたとき、子ども \(i\) の目標個数を \(T_i\) とします。

• \(A_i < T_i\) なら、その子は \(T_i-A_i\) 個もらう必要がある
• \(A_i > T_i\) なら、その子は余っている

1 回の操作で増やせるのは 1 人の 1 個だけなので、必要な操作回数は少なくとも [ \sum \max(0, T_i-A_i) ] です。

逆に、総数は変わらないので、不足分の総和と余剰分の総和は一致します。
したがって、不足している子に余っている子から 1 個ずつ移せば、ちょうどこの回数で実現できます。

よって、操作回数 = 足りない分の合計です。

---

3. どの子を \(q+1\) 個にすればよいか

ここが重要です。

最終的に \(q+1\) 個になる子は \(r\) 人いますが、誰をそうするのが最適でしょうか？

直感的には、もともと多く持っている子を \(q+1\) にした方が得です。
少ない子を \(q+1\) にすると、余計に補充しないといけないからです。

そこで \(A\) を昇順にソートします。
すると、最適な割り当ては

• 小さい方から \(N-r\) 人 → 目標 \(q\)
• 大きい方から \(r\) 人 → 目標 \(q+1\)

です。

つまり、ソート後の配列を \(a\) とすると、目標配列は [ [q,\dots,q,q+1,\dots,q+1] ] と同じ順に対応させればよいです。

---

4. なぜシミュレーションはだめか

素朴に「毎回最大と最小を取り出して 1 個動かす」をシミュレーションすると、
優先度付きキューを使っても 1 回ごとに \(O(\log N)\) かかります。

しかし操作回数そのものが非常に大きくなり得ます。
たとえば \(N=2, A=[0,10^9]\) なら、答えは \(5\times 10^8\) 回です。

このため、1 回ずつ操作する方法は到底間に合いません。
最終状態を直接考えて、必要な移動総数を一気に求める必要があります。

アルゴリズム

1. \(S=\sum A_i\) を求める
2. \(q, r = \mathrm{divmod}(S, N)\) を計算する
3. 配列 \(A\) を昇順ソートする
4. ソート後の前半 \(N-r\) 個の目標を \(q\)、後半 \(r\) 個の目標を \(q+1\) とする
5. それぞれについて足りない分だけ加算する [ \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. ans を出力する

具体例

例えば [ A=[0,1,8,9],\ N=4 ] とします。

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

最終状態は [ [4,4,5,5] ] です。

ソート済みの \(A\) はそのまま [ [0,1,8,9] ] なので、不足分は

• \(0 \to 4\) : 4 個不足
• \(1 \to 4\) : 3 個不足
• \(8 \to 5\) : 不足なし
• \(9 \to 5\) : 不足なし

合計 [ 4+3=7 ] よって答えは 7 です。

計算量

• 時間計算量: \(O(N \log N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• r = 0 のときは全員の目標が \(q\) 個になります。コードでは border = n - r として自然に処理できます。

• 答えは大きくなるので、C++ なら long long が必要です。Python ではそのままで大丈夫です。

• 入力が大きいので、Python では sys.stdin.buffer.read() のような高速入力が有効です。

  ソースコード

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()

---

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