📝 题目大意

给定整数 $N$（$2 \leq N \leq 10^5$），在所有满足 $a + b = N$ 的正整数对 $(a, b)$ 中，求 $a$ 的各位数字之和与 $b$ 的各位数字之和的最小值。

💡 解题思路

1. 题目分析：核心是十进制加法中进位与数字和的关系。设 $S(x)$ 表示 $x$ 的十进制各位数字之和。两个数相加时，每发生一次进位，总数字和会减少 $9$（因为 $10$ 进到高位变成 $1$，净损失 $9$）。因此有恒等式：

   $$S(a) + S(b) = S(N) + 9 \times c$$

   其中 $c$ 为 $a+b$ 过程中产生的进位次数。要最小化 $S(a) + S(b)$，等价于最小化进位次数 $c$。

2. 算法推导：

   • 理想情况：零进位。如果能够构造一对 $(a, b)$ 使得加法过程中不发生任何进位，则 $S(a) + S(b) = S(N)$，这是理论下界。对于绝大多数 $N$，这是可以做到的：只需将 $N$ 的每一位数字 $d_i$ 拆分为 $x_i + y_i = d_i$（$x_i, y_i \ge 0$），并保证 $a$ 和 $b$ 各自至少有一位非零（即 $a, b$ 均为正数）。例如 $N=15$，$a=10, b=5$，$S(10)+S(5)=1+5=6=S(15)$。
   • 特殊情况：$S(N)=1$。此时 $N$ 是 $10$ 的幂（如 $10, 100, 1000, \dots$），其十进制表示仅有一个 $1$ 后面跟若干 $0$。由于只有一位非零数字且为 $1$，无论怎么拆分，都无法让 $a$ 和 $b$ 同时为正且不进位——若把 $1$ 分给 $a$，$b$ 全为 $0$ 则 $b=0$ 不合法。因此至少需要发生一次进位，$S(a)+S(b)=S(N)+9 \times 1 = 10$。
   • 结论：先计算 $N$ 的数字和 ans，若 ans == 1 则输出 10，否则直接输出 ans。

3. 边界与细节：

   • $N=2$ 时数字和为 $2$，$a=1,b=1$ 即得答案 $2$，正确。
   • $N=10^k$ 时输出 $10$，如样例 $N=100000$ 输出 $10$。
   • 数据范围 $N \le 10^5$，int 足够，无溢出风险。

⏱️ 复杂度分析

• 时间复杂度：$O(\log_{10} N)$，即 $N$ 的十进制位数，每次循环提取一位数字。对于 $N \le 10^5$，最多 $6$ 次迭代。
• 空间复杂度：$O(1)$，仅使用常数个变量。

💻 标准代码 (C++)

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, a[100000], ans = 0;  // ans 累加各位数字和
    cin >> n;
    while (n) {
        ans += n % 10;          // 取最低位数字累加
        n /= 10;                // 去掉最低位
    }
    if (ans == 1) ans += 9;     // 数字和为 1 说明 N 是 10 的幂，必须进位一次
    cout << ans;
    return 0;
}