题解

思路

首先判断可行性。除单独的数字 $0$ 外，$s=0$ 无法构成没有前导零的 $m$ 位数；而 $s>9m$ 超过全部数位能提供的最大和。其余情况一定可行。

最大数应让高位尽量大，所以从左到右依次放入不超过剩余数位和的最大数字。最小数则要先保证首位非零，再让较大的数字尽量靠右。

做法

最大值：维护剩余和，每一位填入 $\min(9,\text{剩余和})$。

最小值：先在首位放 $1$ 并从剩余和中减去 $1$，然后从最右一位向左，把每位填成 $\min(9,\text{剩余和})$。这样首位可能在最后再增加，但始终非零。

特别地，$m=1,s=0$ 时最小值和最大值均为 0。

正确性证明

对最大值，从最高位开始，算法在仍能把剩余和放入后续数位的前提下取到最大可能数字；任何更大的数字都超过当前剩余和，任何更小的数字都会在第一个差异位使结果更小。因此所得数最大。

对最小值，首位预留 $1$ 保证合法。剩余数位和从低位向高位尽量填满，等价于让每个高位在满足后缀容量的前提下尽量小。若另一合法数更小，则在首个差异位使用了更小数字，会迫使其后缀承载超过容量的数位和，矛盾。因此所得数最小。

复杂度分析

时间复杂度为 $O(m)$，空间复杂度为 $O(m)$。

子任务说明

• $m\le6$ 时可枚举全部候选整数。
• $m\le20$ 时可做数位和可行性动态规划并逐位重构。
• 满数据直接贪心分配极端数位。