526互联

AtCoder Beginner Contest 307 G Approximate Equalization

发布时间 2023-06-26 15:20:22作者: zltzlt

洛谷传送门

AtCoder 传送门

考虑我们如果确定了最终态 \(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;
}