问题描述
p1583原题链接：UVaOJ 1583 - Digit Generator
相关说明：本题为《算法竞赛入门经典（第2版）》例题 3-5
解法一：暴力（缩小范围）
由于 $1 \leq N \leq 10000$, 能够得到的最大数字和为 MAX_SUM = digit_sum(99999) = 45, 因此可从 $N-45$ 开始枚举（注意边界），计算当前数字是否是最小生成元，而不用每次都从头开始。由于枚举顺序，第一个找到的生成元就是最小生成元。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include <bits/stdc++.h> using namespace std; int main() { const int MAX_SUM = 45; int t, n; cin >> t; while (t--) { int res = 0; cin >> n; for (int i = max(1, n - MAX_SUM); i < n; ++i) { int digit_sum = 0, cur = i; while (cur) { digit_sum += cur % 10; cur /= 10; } if (i + digit_sum == n) { res = i; break; } } cout << res << endl; } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 |
MAX_SUM = 45 t = int(input()) for _ in range(t): res = 0 n = int(input()) for cur in range(max(1, n - MAX_SUM), n): digit_sum = sum([int(x) for x in str(cur)]) if cur + digit_sum == n: res = cur break print(res) |
这里的 MAX_SUM 可以进一步优化，动态地获取 MAX_SUM = 9 * min(len(str(n)), 5).
解法二：暴力（预处理）
分析一下时间复杂度，解法一的时间复杂度为 $O(T * \text{max_sum})$，当 $T$ 的值非常非常大时，使用 Python 是有可能超时的。因此还有进一步优化的做法，即根据输入用例的范围，提前将所有对应的结果计算出来，存储在可查询的数据结构中，这种做法又叫 “预处理“ 或 “打表“。时间复杂度为构造表的时间加上查询表的时间 $O(N+T)$. 对于 $T$ 比较大的情况，能带来指数级别（ MAX_SUM ）的效率提升。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <bits/stdc++.h> using namespace std; int main() { const int MAX_SUM = 45, RANGE = 100100; array<int, RANGE> ans = {0}; for (int i = 1; i <= RANGE - MAX_SUM; ++i) { int digit_sum = 0, cur = i; while (cur) { digit_sum += cur % 10; cur /= 10; } if (!ans[i + digit_sum] || i < ans[i + digit_sum]) ans[i + digit_sum] = i; } int t, n; cin >> t; while (t--) { cin >> n; cout << ans[n] << endl; } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
from collections import defaultdict RANGE = 100100 ans = defaultdict(int) for cur in range(1, RANGE): digit_sum = sum([int(x) for x in str(cur)]) if not ans[cur + digit_sum] or cur < ans[cur + digit_sum]: ans[cur + digit_sum] = cur t = int(input()) for _ in range(t): n = int(input()) print(ans[n]) |
