考虑我们如果确定了最终态 \(B = (B_1, B_2, ..., B_n)\)，如何计算最少操作次数。
显然从左往右依次使 \(A_i = B_i\)。当操作到第 \(i\) 个位置时，此时 \(A'_i = \sum\limits_{j = 1}^i A_j - B_j\)，所需操作次数为 \(|A'_i|\)。令 \(C_i = \sum\limits_{j = 1}^i A_j - B_j\)，最少操作次数为 \(\sum\limits_{i = 1}^n |C_i|\)。
设 \(s = \sum\limits_{i = 1}^n A_i, r = s \bmod n\)，那么最终态一定有 \(r\) 个 \(\left\lfloor\frac{s}{n}\right\rfloor + 1\)，\(n - r\) 个 \(\left\lfloor\frac{s}{n}\right\rfloor\)。考虑 dp，设 \(f_{i, j}\) 为考虑到第 \(i\) 个位置，当前有 \(j\) 个 \(\left\lfloor\frac{s}{n}\right\rfloor + 1\)。转移讨论第 \(i\) 个位置取 \(\left\lfloor\frac{s}{n}\right\rfloor\) 还是 \(\left\lfloor\frac{s}{n}\right\rfloor + 1\) 即可。因为知道 \(j\)，所以 \(C_i\) 能算出来，操作次数也能知道。
时间复杂度 \(O(n^2)\)。
code
// Problem: G - Approximate Equalization
// Contest: AtCoder - Tokio Marine & Nichido Fire Insurance Programming Contest 2023（AtCoder Beginner Contest 307)
// URL: https://atcoder.jp/contests/abc307/tasks/abc307_g
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 5050;
ll n, a[maxn], f[maxn][maxn], b[maxn];
void solve() {
scanf("%lld", &n);
ll s = 0;
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
s += a[i];
}
ll r = (s % n + n) % n;
s = (s - r) / n;
for (int i = 1; i <= n; ++i) {
b[i] = b[i - 1] + a[i] - s;
}
mems(f, 0x3f);
f[0][0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= i; ++j) {
f[i][j] = f[i - 1][j];
if (j) {
f[i][j] = min(f[i][j], f[i - 1][j - 1]);
}
f[i][j] += abs(b[i] - j);
}
}
printf("%lld\n", f[n][r]);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}