自动搬运

查看原文

来自洛谷，原作者为

	ddxrS_loves_zxr 一个诗意的个性签名

搬运于2025-08-24 23:06:54，当前版本为作者最后更新于2025-02-05 01:12:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先让我们考虑一个贪心。

想要得到 $1$，就只能是通过将 $100\dots 0$ 循环右移一次，而得到 $100\dots 0$ 只能是将 $99\dots 9+1$ 或者原本的 $n$ 就是这个样子。

那么对于给定的 $n$，若其最低位 $0<c<9$，那么增加 $9-c$ 次，然后位移；若 $c=0$ 就直接位移。

执行上述操作直到 $n$ 全部变为 $9$，然后再花费两次变成 $1$。

这个贪心可以通过子任务 $1,2$。

这个贪心显然是错的，比如当 $n=\underbrace{99\dots 9}_{10^6-2\text{ 个}}89$ 时，进行 $10$ 次增加操作要优于 $10^6-1$ 次位移操作。

问题在于我们并不能够确定位移操作的执行次数，在某些情况下使用增加操作去代替位移操作可能是更优的。

假设要进行 $k$ 次位移操作，我们将 $n$ 分成两段：一段包含前 $k$ 个非零数位以及在其之后接上的 $0$；另一段包含剩下的数位。分别记作前缀 $p$ 和后缀 $s$。

例如在 $n=120030005607$ 和 $k=3$ 时 $p=12003000,s=5607$。

我们的策略是，先对后缀 $s$ 进行增加操作，直到后缀全变成 $9$，需要做 $\underbrace{99\dots 9}_{s\text{ 的长度个}}-s$ 次。

之后再按照最开始的贪心来处理前缀 $p$，这部分要 $k+\sum9-c_i$ 次。

同时先进行位移操作再将后缀 $s$ 全部变为 $9$ 是不优的，因为你进行位移操作过后，将 $s$ 变为 $9$ 的代价会增加 $10$ 倍。

令 $n$ 的长度为 $m$，那么时间复杂度为 $O(m^2)$。

可以发现，对后缀 $s$ 进行很多次增加操作是不会优于直接贪心的。

贪心最多只会耗费 $10^7$ 次操作，因此我们只需要枚举使得后缀 $s$ 增加的次数不超过 $10^7$ 次的情况。

令 $t$ 表示 $n$ 中非零数位的数量，那么只需要 $t-7\le k\le t$。

还存在一种情况就是存在一种后缀形如 $99\dots 9ABCDEFG$，这种后缀的增加次数也不会超过 $10^7$。

所以总共需要考虑的情况只有 $O(1)$ 种，时间复杂度 $O(m)$。

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e6 + 5;
int n, k;
string s;
ll solve(int r) {
    ll sum = r, i, j, tot = 0, tmp = 0;
    for(i = 1, j = 0; i <= n && j < r; i++) if(s[i] > '0') sum += '9' - s[i], j++;
    while(i <= n && s[i] == '0') i++;
    while(i <= n && s[i] == '9') i++;
    if(n - i + 1 > 7) return 0x3f3f3f3f3f3f3f3f;
    for(; i <= n; i++) tot = tot * 10 + 9, tmp = tmp * 10 + s[i] - '0';
    return sum + tot - tmp;
}
int main() {
#ifdef ddxrS
    freopen("sample.in", "r", stdin);
    freopen("sample.out", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>s; n = s.length(), s = '#' + s;
    for(int i = 1; i <= n; i++) k += (s[i] != '0');
    if(k == 1 && s[1] == '1' && n == 1) return cout<<0<<'\n', 0;
    if(k == 1 && s[1] == '1') return cout<<1<<'\n', 0;
    ll ans = 0x3f3f3f3f3f3f3f3f, lst = n;
    for(int i = n - 7; i >= 0; i--) if(s[i] != '9') {lst = i; break;} 
    for(int i = max(0, k - 7); i <= k; i++) ans = min(ans, solve(i));
    cout<<min(ans, solve(lst)) + 2<<'\n';
    return 0;
}