解题思路

定义 “好数”是十进制表示中恰有一个非零位的正整数，即形如 $d\times 10^k$（$d\in[1,9],\,k\ge0$），例如 $7, 40, 3000$。

分解与独立性 对不同下标的元素操作互不影响，所以总答案是各元素独立变成好数的最小代价之和。问题归约为：给定一个正整数 $x$，用如下操作的最少次数把它变成好数：

1. $x\leftarrow x+1$；
2. 若 $x>1$，则 $x\leftarrow x-1$；
3. 若 $x$ 是 10 的倍数，则 $x\leftarrow x/10$。

核心思想（数位 DP + 记忆化搜索） 把“/10”看成“删去末位”的强力操作，但只有在末位为 0 时才可用。因此对任意 $x$，有三种策略取最小：

• 直接停到某个好数：只用 $\pm1$ 把 $x$ 调到最近的好数 $d\cdot 10^k$。代价为 $\min_{k,d}|x-d\cdot10^k|$。
• 向下凑整再除：若 $x\ge 10$，先把末位调成 0（代价 $x\bmod 10$），再做一次除 10（代价 1），得到 $\lfloor x/10\rfloor$，继续递归。
• 向上凑整再除：把末位往上调到 0（代价 $10-(x\bmod10)$；当 $x\le 9$ 时只能走这条，因为不能从 1 递减到 0），再除 10（代价 1），得到 $\lceil x/10\rceil$，继续递归。

于是对单个数的最小代价满足如下递推（记 $r=x\bmod10$）：

并以“已是好数时 $\text{dp}(x)=0$”为边界。由于每次除 10 都把规模缩小一位，递归深度仅为 $\mathcal{O}(\log_{10} x)$。用 记忆化搜索 即可线性去重。

最后答案为 $\sum_{i=1}^{n} \text{dp}(a_i)$。

为什么需要“除 10”分支？ 直接就近到好数的代价可能很大（比如从 12345 到 12000 要 345 步），而“凑整 + 除 10”可以快速消掉低位：

总代价 $5+1+4+1+3+1+2=17$，远小于 345。

复杂度分析

• 设最大输入值为 $A=\max a_i$（题目中 $A\le 2\times10^5$）。
• 每个状态 $x$ 的转移仅依赖 $\lfloor x/10\rfloor$、$\lceil x/10\rceil$ 和一次“直接就近好数”的常数候选（$k$ 约 0～6，$d=1..9$，共 $\le 63$ 个）。
• 记忆化后唯一状态数为 $\mathcal{O}(A)$，因此总时间复杂度约为 $\mathcal{O}(A\cdot 63)$，在本约束内非常稳健；空间复杂度 $\mathcal{O}(A)$。

代码实现

Python

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(1 << 25)

# 判断是否为好数：十进制恰一位非零
def is_good(x: int) -> bool:
    cnt = 0
    t = x
    while t > 0:
        if t % 10 != 0:
            cnt += 1
            if cnt > 1:
                return False
        t //= 10
    return cnt == 1

# 预生成候选好数 d*10^k（覆盖到 10 * maxA 的量级即可）
def build_goods(maxA: int):
    goods = []
    p = 1
    while p <= 10 * maxA:  # 向上多一位，保证“下一阶”也被覆盖
        for d in range(1, 10):
            goods.append(d * p)
        p *= 10
    goods.sort()
    return goods

def main():
    data = list(map(int, sys.stdin.read().strip().split()))
    n = data[0]
    arr = data[1:]
    maxA = max(arr) if arr else 1
    goods = build_goods(maxA)

    from functools import lru_cache

    # 计算 x 到最近好数的“直接挪动”代价（只用 ±1）
    def direct_cost(x: int) -> int:
        # 扫描固定常数个候选，取最小差值
        # goods 已排序，但顺扫 60 余个也足够快
        best = 1 << 60
        for g in goods:
            # 小优化：大到离谱时可提前中断
            diff = abs(x - g)
            if diff < best:
                best = diff
            # 若 g 已远大于 x 且差值开始增大，可剪枝
            if g > x and diff > best:
                break
        return 0 if is_good(x) else best

    @lru_cache(maxsize=None)
    def dp(x: int) -> int:
        # 已经是好数，代价为 0
        if is_good(x):
            return 0

        r = x % 10
        ans = direct_cost(x)  # 直接到最近好数

        # 向下凑整再除（x>=10 才能安全往下凑到 ...0）
        if x >= 10:
            down = r + 1 + dp(x // 10)  # 末位减到 0，用 1 次 /10
            if down < ans:
                ans = down

        # 向上凑整再除（x<=9 时只能向上）
        up_step = (10 - r) if x >= 10 else (10 - x)
        up = up_step + 1 + dp((x + up_step) // 10)
        if up < ans:
            ans = up

        return ans

    total = 0
    for v in arr:
        total += dp(v)

    print(total)

if __name__ == "__main__":
    main()

Java

// Java 17，ACM 风格，类名 Main
// 思路：记忆化搜索 + 数位操作。dp(x)= min(直接到好数, 向下凑整除, 向上凑整除)
import java.io.*;
import java.util.*;

public class Main {
    static ArrayList<Integer> goods = new ArrayList<>();
    static HashMap<Integer, Integer> memo = new HashMap<>();

    // 判断是否为好数：十进制恰一位非零
    static boolean isGood(int x) {
        int cnt = 0, t = x;
        while (t > 0) {
            if (t % 10 != 0) {
                cnt++;
                if (cnt > 1) return false;
            }
            t /= 10;
        }
        return cnt == 1;
    }

    // 生成候选好数 d*10^k，覆盖到 10 * maxA
    static void buildGoods(int maxA) {
        goods.clear();
        long p = 1;
        while (p <= 10L * maxA) {
            for (int d = 1; d <= 9; d++) {
                goods.add((int)(d * p));
            }
            p *= 10;
        }
        Collections.sort(goods);
    }

    // 只用 ±1 把 x 调到最近好数的代价
    static int directCost(int x) {
        if (isGood(x)) return 0;
        int best = Integer.MAX_VALUE;
        for (int g : goods) {
            int diff = Math.abs(x - g);
            if (diff < best) best = diff;
            if (g > x && diff > best) break; // 轻度剪枝
        }
        return best;
    }

    static int dp(int x) {
        if (isGood(x)) return 0;
        if (memo.containsKey(x)) return memo.get(x);

        int r = x % 10;
        int ans = directCost(x);

        if (x >= 10) {
            int down = r + 1 + dp(x / 10); // 向下凑整 + /10
            if (down < ans) ans = down;
        }

        int upStep = (x >= 10) ? (10 - r) : (10 - x);
        int up = upStep + 1 + dp((x + upStep) / 10);
        if (up < ans) ans = up;

        memo.put(x, ans);
        return ans;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 读取 n
        int n = Integer.parseInt(br.readLine().trim());
        String[] parts = br.readLine().trim().split("\\s+");
        int[] a = new int[n];
        int maxA = 1;
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(parts[i]);
            if (a[i] > maxA) maxA = a[i];
        }

        buildGoods(maxA);

        long sum = 0L;
        for (int v : a) {
            sum += dp(v);
        }
        System.out.println(sum);
    }
}

C++

// C++17，ACM 风格
// 记忆化 dp：dp(x)= min(直接到最近好数, 向下凑整后/10, 向上凑整后/10)
#include <bits/stdc++.h>
using namespace std;

static vector<int> goods;
static unordered_map<int,int> memo;

// 判断是否为好数：十进制恰一位非零
bool isGood(int x) {
    int cnt = 0;
    while (x > 0) {
        if (x % 10 != 0) {
            cnt++;
            if (cnt > 1) return false;
        }
        x /= 10;
    }
    return cnt == 1;
}

// 生成候选好数 d*10^k，覆盖到 10 * maxA
void buildGoods(int maxA) {
    goods.clear();
    long long p = 1;
    while (p <= 1LL * 10 * maxA) {
        for (int d = 1; d <= 9; ++d) {
            goods.push_back((int)(d * p));
        }
        p *= 10;
    }
    sort(goods.begin(), goods.end());
}

// 只用 ±1 把 x 调到最近好数的代价
int directCost(int x) {
    if (isGood(x)) return 0;
    int best = INT_MAX;
    for (int g : goods) {
        int diff = abs(x - g);
        if (diff < best) best = diff;
        if (g > x && diff > best) break; // 简单剪枝
    }
    return best;
}

int dp(int x) {
    if (isGood(x)) return 0;
    auto it = memo.find(x);
    if (it != memo.end()) return it->second;

    int r = x % 10;
    int ans = directCost(x);

    if (x >= 10) {
        int down = r + 1 + dp(x / 10); // 向下凑整 + /10
        ans = min(ans, down);
    }

    int upStep = (x >= 10) ? (10 - r) : (10 - x);
    int up = upStep + 1 + dp((x + upStep) / 10);
    ans = min(ans, up);

    memo[x] = ans;
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; 
    if (!(cin >> n)) return 0;
    vector<int> a(n);
    int maxA = 1;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        maxA = max(maxA, a[i]);
    }

    buildGoods(maxA);

    long long sum = 0;
    for (int v : a) sum += dp(v);
    cout << sum << "\n";
    return 0;
}

题目内容

小美定义一个正整数 $x$ 是 好的，当且仅当其十进制表示中仅包含一个非零有效位，例如 $4000、9、20$ 都是好的数，而 $110、301、6666$ 不是好的数，非正整数也不是好的数；

给定一个长度为 $n$ 的正整数数组 {$a_1,a_2,...,a_n$}，你可以对数组执行若干次以下三种操作中的一种：

选择一个索引 $i$ ，将 $a_i$ 增加 $1$ ；

选择一个索引 $i$ ，如果 $a_> 1$，则将 $a_i$ 减少 $1$ ；

选择一个素引 $i$ ，如果 $a_i$ 是 $10$ 的整数倍，则将 $a_i$ 除以 $10$ ，否则该操作无效；

输出将数组中所有元素都变为好的数所需的最少操作次数。

输入描述

第一行输入一个整数 $n(1 ≤n≤2 × 10^5)$ ，表示数组的长度；

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(1 ≦a_i≦n)$ ，表示数组的初始元素。

输出描述

输出一个整数，表示将数组中所有元素都变为好的数的最少操作次数。

样例1

输入

3
1 2 3

输出

0

样例2

输入

11
11 1 1 1 4 5 6 7 8 9 10

输出

1

说明

将 $11$ 减一得 $10$ ；