题解

思路

记 $S(x)$ 为 $x$ 的数位和。

做法

竖式加法中每产生一次进位，$S(a+b)$ 就比无进位时减少 $9$，所以目标等价于让进位尽可能多。若最优方案存在进位，可以循环移动数位，使最低位先产生一次进位，之后连续进位的每一位只需两数位之和至少为 $9$。枚举 $a$ 的最低位数字，给它配对能使和至少为 $10$ 的最小数字；其余数字从小到大贪心配对满足和至少为 $9$ 的最小数字，未配对数字放到高位。

复杂度

九种起点分别构造并实际计算数位和，取最优者即可，时间复杂度为 $O(|a|+|b|)$，空间复杂度为 $O(|a|+|b|)$。