数位和 题解

题目分析

本题要求我们从给定的 $n$ 个正整数中，找出数位和的最大值。数位和的定义很简单：将一个数的每一位数字相加，例如 $12345$ 的数位和为 $1+2+3+4+5=15$。

题目给出的数据范围：$n \le 10^5$，每个正整数不超过 $10^{12}$。因此，每个数的位数不超过 $13$ 位（$10^{12}$ 是 $13$ 位数），数位和最大为 $9 \times 13 = 117$，结果可以用 int 类型存储。

解题思路

由于题目只要求求出最大值，我们可以采用模拟的方法：

1. 读入 $n$ 和接下来的 $n$ 个正整数。
2. 对于每个整数，通过循环取个位并累加的方式计算其数位和：
   • 每次取出个位数字（tmp % 10），累加到当前数的数位和中。
   • 然后将整数除以 $10$，去掉个位。
   • 重复以上步骤直到整数变为 $0$。
3. 用一个变量 max_sum 维护当前所有数位和的最大值，每计算完一个数的数位和就尝试更新。
4. 最后输出最大值即可。

这种方法直接明了，不需要额外的数据结构或复杂算法。

算法说明

算法名称：模拟 + 取余法求数位和

算法步骤：

1. 初始化答案变量 ans = 0。
2. 循环 $n$ 次，每次读入一个正整数 $x$：
   • 设置临时和 sum = 0。
   • 当 $x>0$ 时：
     • sum += x % 10 （取个位累加）
     • x /= 10 （去掉个位）
   • ans = max(ans, sum)
3. 输出 ans。

该算法清晰可靠，适合处理大数量的正整数。

时间复杂度分析

对于每个数字，我们需要逐位取出数字，每个数字的位数最多为 $d = \lfloor \log_{10}(10^{12}) \rfloor + 1 = 13$ 位左右，因此每个数字的计算时间为 $O(d)$。对于 $n$ 个数字，总时间复杂度为 $O(n \cdot d) \approx O(13n) = O(n)$。空间复杂度仅为 $O(1)$，非常高效，完全满足 $n \le 10^5$ 的要求。

参考代码

cpp
复制
1#include <bits/stdc++.h>
2using namespace std;
3#define ll long long
4
5int main() {
6    int n;
7    cin >> n;           // 读入正整数个数
8    int max_sum = 0;    // 维护最大数位和
9
10    for (int i = 0; i < n; i++) {
11        int digit_sum = 0;  // 当前数字的数位和
12        ll num;             // 用 long long 避免溢出
13        cin >> num;
14
15        // 循环取出每一位并累加
16        while (num > 0) {
17            digit_sum += num % 10;
18            num /= 10;
19        }
20
21        // 更新最大值
22        max_sum = max(max_sum, digit_sum);
23    }
24
25    cout << max_sum << endl;  // 输出结果
26    return 0;
27}

代码解释

• n 存储数字个数，max_sum 记录遍历过程中遇到的最大数位和。
• 变量 num 使用 long long 类型，因为输入的正整数最大可达 $10^{12}$，在 int 可能溢出的边缘（$10^{12}>2^{31}-1$），所以使用 long long 更安全。
• 对于每个 num，digit_sum 用于累加数位。while(num > 0) 循环执行以下操作：
  • num % 10 获取当前最低位数字，累加到 digit_sum。
  • num /= 10 将最低位移除，继续处理下一位。
• 使用 max() 函数更新最大值。
• 最后输出 max_sum。

注意事项

• 单个数字的数位和可能为零吗？题目中均为正整数，所以至少为 $1$，但即使为 $0$，我们的代码也能正确处理。
• 使用 long long 类型读取数据是必要的，因为 $10^{12}$ 超出了 32 位 int 的范围。
• 每次循环重新初始化 digit_sum = 0，避免上一次的计算结果影响当前数字。

这道题考察了对整数位操作的掌握，属于简单模拟题，细心就能满分通过。