数列 \(A\) に対して操作を繰り返し行った後の数列を \(B\) とします。操作の前後で数列の要素の総和は変わらないので、\(A\) の要素の総和と \(B\) の要素の総和は等しい必要があります。以下これを仮定します。

この問題は以下の \(2\) つの部分問題に分けられます。

1. \(B\) を \(1\) つ決め打ったとき、\(A\) を \(B\) と一致させるのに必要な最小の操作回数を求める
2. 最大値と最小値の差が \(1\) 以下であるような \(B\) のうち、1. で求めた操作回数が最小になるものを求める

1. \(B\) を \(1\) つ決め打ったとき、\(A\) を \(B\) と一致させるのに必要な最小の操作回数を求める

すべての \(k\ (1 \leq k \leq N)\) に対する \(|A_k - B_k|\) の総和を \(S\) とします。\(1\) 回の操作において、\(A_i\) を \(1\) 減らすことによる \(S\) の変化量は \(\pm 1\)、\(A_j\) を \(1\) 増やすことによる \(S\) の変化量も \(\pm 1\) ですから、\(1\) 回の操作で \(S\) は最大 \(2\) 減少することになります。今、操作の目的は \(A\) を \(B\) と一致させること、すなわち \(S\) を \(0\) にすることですから、\(\frac{S}{2}\)（この値は整数になることが証明できます）回以上の操作が明らかに必要です。逆に、うまく操作を行えば、\(\frac{S}{2}\) 回の操作で必ず \(A\) を \(B\) と一致させることができます。

よって、この部分問題の答えは \(\displaystyle \frac{\sum_{k = 1}^{N} |A_k - B_k|}{2} \) と表せます。余談ですが、これは多くの中高難度問題において部分問題として出題されているものなので、結果の式を覚えてしまってもよいかもしれません。

2. 最大値と最小値の差が \(1\) 以下であるような \(B\) のうち、1. で求めた操作回数が最小になるものを求める

まず、

• \(B\) の要素の総和は \(A\) の要素の総和と等しい
• \(B\) の最大値と最小値の差は \(1\) 以下である

という条件を満たすためには、\(A\) の要素の総和を \(N\) で割ったときの商を \(p\)、余りを \(r\) とすると、\(B\) は \(N-r\) 個の \(p\) と \(r\) 個の \(p+1\) から構成される必要があります。

1. の結果も用いると、本問題は以下の問題に帰着されます。

• \(N-r\) 個の \(p\) と \(r\) 個の \(p+1\) から構成されるような \(B\) のうち、\(\displaystyle \sum_{k = 1}^{N} |A_k - B_k|\) を最小にするものを求めよ。

直感的には、\(A_i\) が小さい順に \(i = 1,2,\dots,N\) を並び替えたとき、先頭の \(N-r\) 個の \(i\) について \(B_i =p\)、末尾の \(r\) 個の \(i\) について \(B_i =p+1\) とする（つまり、小さい \(A\) に小さい \(B\) を、大きい \(A\) に大きい \(B\) を割り当てる）のが最適に思われます。実際この直感は正しいです。

よってこの問題は、\(A\) のソートがボトルネックとなり \(O(N \log N)\) で解くことができます。下記の実装例も参考にしてください。なお、std::nth_element などを用いれば \(O(N)\) で解くこともできます。

実装例 (C++) :

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    ll sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    sort(a.begin(), a.end());
    vector<int> b(n, sum / n);
    for (int i = 0; i < sum % n; i++) {
        b[n - 1 - i]++;
    }
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ans += abs(a[i] - b[i]);
    }
    cout << ans / 2 << endl;
}

実装例 (Python) :

n = int(input())
a = list(map(int, input().split()))
sum = sum(a)
a.sort()
b = [sum // n for i in range(0, n)]
for i in range(0, sum % n):
    b[n - 1 - i] += 1
ans = 0
for i in range(0, n):
    ans += abs(a[i] - b[i])
print(ans // 2)