Loading... # 题目描述 小苯有两个区间 $[l_1, r_1]$ 和 $[l_2, r_2]$，他想要在两个区间中各取一个数字求和（结果记为 $sum$），他希望最大化 $sum$ 的数位和。 （数位和定义为数字的各个数位之和，例如 $123$ 的数位和为 $6$。） # 输入 每个测试文件内都包含多组测试数据。 第一行一个正整数 $T\ (1 \leq T \leq 10000)$，表示测试数据的组数。 接下来对于每组测试数据，输入包含一行四个整数 $l_1, r_1, l_2, r_2\ (1 \leq l_1, l_2, r_1, r_2 \leq 10^{18}, l_1 \leq r_1, l_2 \leq r_2)$ # 输出 对于每组测试数据，输出一行一个整数表示最大的数位和。 # 解题思路 ## 简化题目 阅读题目不难发现， 对于$x \in [l1, r1]$和$y \in [l2, r2]$， 求$x+y$的数位和相当于求$z\in[l, r]$中$z$的数位和， 其中$l=l1+l2, r=r1+r2$ ## 贪心思路 - 当$l$和$r$的数位不同， 如$l=1234$, $r=12345$, 此时显然数位和最大为$9999$， 即将$r$的最高位减$1$， 将其余位置变为$9$ - 当$l$和$r$数位相同时，此时可以采用下面的贪心策略： - 设初始的最大数位和对应的数字是$r$，现在从左向右遍历$l$和$r$的每一位， 如果$l[i]<r[i]$: - 如果对于$\forall j > i$都有$r[j]==9$，则原数$r$就是数位和最大的数字 - 如果$\exists j > i\wedge r[j]!=9$，则将当前位减一， 后面的每一位都变成9就是数位和最大的数字 - 否则，则继续遍历$i+1$的位置 # AC代码 ```cpp #include <cstdio> #include <cstdlib> #include <iostream> #include <cstring> #define endl '\n' using namespace std; const int N = 2e5 + 10; typedef long long LL; int count(LL x) { int ans = 0; while(x) { ans = ans + x % 10; x = x / 10; } return ans; } int solve(LL l, LL r) { string sl = to_string(l); string sr = to_string(r); if(sl.size() != sr.size()) { string tmp; for(int i = 0; i < sr.size() - sl.size(); i ++) tmp += '0'; sl = tmp + sl; } string tmp; bool flag = true; for(int i = 0; i < sl.size(); i ++) { if(sl[i] < sr[i]) { tmp += (sr[i] - 1); for(int j = i + 1; j < sr.size(); j ++) { if(sr[j] != '9') { flag = false; } tmp += '9'; } break; } tmp += sr[i]; } LL ans; if(flag) ans = stoll(sr); else ans = stoll(tmp); return count(ans); } int t; LL l1, r1, l2, r2; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> t; while(t --) { cin >> l1 >> r1 >> l2 >> r2; int a = solve(l1 + l2, r1 + r2); cout << a << endl; } return 0; } ``` 最后修改：2025 年 01 月 11 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏