题意

给定一个数字 （数据范围版本之间存在差异），你可以多次对 进行 ，但是仅能进行一次 ，求使得操作最终的结果变为 的最少操作次数，有多测。

思路

我们下面只考虑 Hard 版本。

我们假设最终结果是 ，且一定会用一次 。那么， 这个操作必然会被 分成两部分，一部分是 之前加的，另一部分就是之后加的。

我们设前半部分的 次数为 ，后半部分次数为 。

于是有：，令 ，显然 。

设有 个 的 为 ，那我们只要枚举比 严格大的 ，于是我们可以知道 ，贪心的想，多用 是更优的，那我们直接令 。于是我们的答案就是 的最小值。

一般情况大致就是上面的解法了。

接下来说两个特判：

1. 输入的 已经满足要求：输出 ；
2. 输入的 已经是 的倍数：那我们可以找到一个比 大的 ，先直接计算不使用 操作的操作次数，然后再与一般情况得到的操作次数取 就好了。

简单单个测试点的复杂度很好估计，就是 级别的，于是总复杂度就是 ，可以通过。

Code

const u64 N = 9e18;
const int M = 100;
u128 f[M];

inline bool check(u128 x) {
	while (x) {
		if (x % 10 != 9) return false;
		x /= 10;
	}
	return true;
}

inline u128 find(u128 x) {
	for (u128 k = 9; ; k = k * 10 + 9) if (k > x) return k;
}

void solve() {
	u128 x;
	read(x);

	if (check(x)) { write(0), putchar('\n'); return;}

	int pos = -1;
	for (int i = 0; i < M; i++) if (f[pos] > x) { pos = i; break; }

	u128 ans = INF64;
	if (x % 9 == 0) {
		u128 t = find(x);
		ans = std::min(ans, (t - x) / 9);
	}

	for (int i = pos; i < M; i++)
      ans = std::min((f[i] - x) % 9 + (f[i] - x) / 9 + 1, ans);
	write(ans);
	putchar('\n');
}

signed main() {
	for (u128 i = 0, k = 1; k <= N; i++, k = k * 10 + 1) f[i] = k;
	int T;
	std::cin >> T;
	while (T--) solve();
	return 0;
}

为了稳定和防爆，使用了 uint128 类型，各位需注意。