526互联

AtCoder Regular Contest 153 D Sum of Sum of Digits

发布时间 2023-05-30 20:35:13作者: zltzlt

洛谷传送门

AtCoder 传送门

又浪费一道好题

我首先想的是，\(x\) 显然最优取某些 \(a_i\) 往前进位时的值。然后就误以为 \(x\) 的取值是 \(O(n \log_{10} V)\) 的了……

既然没发现什么性质，那就直接 dp 吧！设 \(f_{d, i}\) 为从低到高前 \(d\) 位，所有 \(a_i\) 进位之和为 \(i\)。然后可以发现，把所有 \(a_i\) 按照 \(a_i \bmod 10^d\) 从大到小排序，在这一位进位的只可能是前面几个值。做完了？

code 
// Problem: D - Sum of Sum of Digits
// Contest: AtCoder - AtCoder Regular Contest 153
// URL: https://atcoder.jp/contests/arc153/tasks/arc153_d
// Memory Limit: 1024 MB
// Time Limit: 5000 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 = 200100;

int n, a[maxn], pw[12], f[12][maxn];

void solve() {
	scanf("%d", &n);
	pw[1] = 1;
	for (int i = 2; i < 12; ++i) {
		pw[i] = pw[i - 1] * 10;
	}
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}
	mems(f, 0x3f);
	f[0][0] = 0;
	for (int d = 1; d <= 10; ++d) {
		sort(a + 1, a + n + 1, [&](int x, int y) {
			return x % pw[d] > y % pw[d];
		});
		for (int k = 0; k <= 9; ++k) {
			int c = 0, s = 0;
			for (int i = 1; i <= n; ++i) {
				c += (((a[i] / pw[d]) % 10 + k) >= 10);
				s += ((a[i] / pw[d]) % 10 + k) % 10;
			}
			f[d][c] = min(f[d][c], f[d - 1][0] + s);
			for (int i = 1; i <= n; ++i) {
				if ((a[i] / pw[d]) % 10 + k == 9) {
					++c;
					s -= 9;
				} else {
					++s;
				}
				f[d][c] = min(f[d][c], f[d - 1][i] + s);
			}
		}
	}
	int ans = 2e9;
	for (int i = 0; i <= n; ++i) {
		ans = min(ans, f[10][i] + i);
	}
	printf("%d\n", ans);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}