问题概述

给定一个正整数 \(n\)（\(1 \le n < 10^{15}\)），要求将其拆分为若干个数之和，每个数只能是仅由数字1构成的整数（可正可负）。目标是使所有加数中包含的数字1的总个数最少。

例如，\(121 = 111 + 11 + (-1)\)，使用了 \(3+2+1 = 6\) 个数字1。

思路分析

记 \(y_k\) 为 \(k\) 个1组成的数，即 \(y_k = \underbrace{111\ldots 1}_{k\text{个}}\)。观察发现，一个 \(y_{k+1}\) 可以用 \(y_k\) 和 \(y_1\) 表示：

\[ y_{k+1} = 10y_k - y_1 \]

首先，将 \(n\) 拆解为各个数位的和，每个数位对应一组 \(y_i\) 的系数。以 \(n = 150\) 为例，其十进制分解为 \(1 \times 10^2 + 5 \times 10^1 + 0 \times 10^0\)，转换后得到：

• \(1\) 个 \(y_3\)（对应 \(10^2\)）
• \(4\) 个 \(y_2\)（因为 \(5 \times 10^1 = 5 \times (10y_1 - y_1)\)，化简后得到）
• \(-5\) 个 \(y_1\)

设 \(a_i\) 为 \(y_{i+1}\) 的系数（下标从0开始，即 \(a_0\) 对应 \(y_1\)，\(a_1\) 对应 \(y_2\)，依此类推）。通过高位变换，可以调整这些系数以减少绝对值和。高位借位规则如下：

• 若 \(a_x > 0\)：可从 \(y_{x+2}\) 借1，使得 \(a_x\) 减少10，\(a_0\) 减少1，\(a_{x+1}\) 增加1。
• 若 \(a_x < 0\)：可向 \(y_{x+2}\) 还1，使得 \(a_x\) 增加10，\(a_0\) 增加1，\(a_{x+1}\) 减少1。

这个方法利用了 \(y_{k+1} = 10y_k - y_1\) 的关系。由于数字长度最多为16（\(10^{15}\) 有16位），因此最多有17种 \(y_i\)。采用深度优先搜索（DFS）遍历每个位置是否借位，最终统计 \(\sum |a_i| \times (i+1)\) 的最小值。

代码实现

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;

typedef long long LL;
const int N = 110;

LL n;
vector<int> digits;
int coeff[N], len, best = 0x3f3f3f3f;

void dfs(int pos) {
    if (pos > len) {
        int total = 0;
        for (int i = 0; i <= len; ++i)
            total += abs(coeff[i]) * (i + 1);
        best = min(best, total);
        return;
    }
    // 不进行任何借位操作
    dfs(pos + 1);
    
    if (coeff[pos] > 0) {
        // 借高位：coeff[pos] -= 10, coeff[0] -= 1, coeff[pos+1] += 1
        coeff[pos + 1] += 1;
        coeff[pos] -= 10;
        coeff[0] -= 1;
        dfs(pos + 1);
        // 回溯
        coeff[0] += 1;
        coeff[pos] += 10;
        coeff[pos + 1] -= 1;
    } else if (coeff[pos] < 0) {
        // 还高位：coeff[pos] += 10, coeff[0] += 1, coeff[pos+1] -= 1
        coeff[pos + 1] -= 1;
        coeff[pos] += 10;
        coeff[0] += 1;
        dfs(pos + 1);
        // 回溯
        coeff[0] -= 1;
        coeff[pos] -= 10;
        coeff[pos + 1] += 1;
    }
}

int main() {
    cin >> n;
    while (n) {
        digits.push_back(n % 10);
        n /= 10;
    }
    len = digits.size();
    // 初始化系数：从高位到低位处理
    for (int i = len - 1; i >= 0; --i) {
        coeff[i] += digits[i];
        if (i) coeff[i - 1] -= digits[i];
    }
    dfs(0);
    cout << best << endl;
    return 0;
}

另一种解法：直接搜索并用预计算

另一种思路是预先生成 \(y_k\) 的数值（直到 \(y_{16}\)），然后对 \(n\) 进行深度优先搜索，每次选择使用还是不使用当前最高位的 \(y_k\)，并尝试用 \(y_k\) 抵消一部分数字，递归到低位。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

typedef long long LL;

// 预计算 y_k = 111...1 (k个1)
LL ones[20] = {0, 1, 11, 111, 1111, 11111, 111111, 1111111, 11111111, 111111111,
               1111111111, 11111111111, 111111111111, 1111111111111,
               11111111111111, 111111111111111, 1111111111111111, 11111111111111111};
LL n, ans = 1e18;

int find_highest(LL x) {
    int l = 1, r = 16;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (x <= ones[mid]) r = mid;
        else l = mid + 1;
    }
    return l;
}

void dfs(int level, LL remaining, LL count) {
    if (level == 0) {
        if (remaining == 0) ans = min(ans, count);
        return;
    }
    int k = find_highest(remaining);
    // 选择1：使用 y_k 并可能再借一个 y_k
    LL borrow = ones[k] - remaining;
    dfs(level - 1, borrow % ones[level], count + borrow / ones[level] * level + k);
    // 选择2：不使用 y_k，直接取模
    dfs(level - 1, remaining % ones[level], count + remaining / ones[level] * level);
}

int main() {
    cin >> n;
    dfs(16, n, 0);
    cout << ans << endl;
    return 0;
}

测试示例

• 输入：121 → 输出：6
• 输入：150 → 输出：15
• 输入：19 → 输出：7
• 输入：111 → 输出：3

总结

两种方法都利用了"借位"思想，将大数分解转化为对系数或数字的调整，最终通过搜索找到最小1的个数。时间复杂度在可接受范围内。