题解

思路

十进制正整数位数越多一定越大，因此先用最便宜数字得到最大位数 $L=\lfloor v/m\rfloor$。在位数固定时，应从高位到低位尽量选择更大的数字。

做法

若 $L=0$，输出 -1。否则依次构造 $L$ 位：对当前位置从数字 9 到 1 尝试，若支付其费用后，剩余油漆仍不少于“剩余位数乘最小费用”，就选择该数字。

正确性证明

任何可行整数的位数不超过 $\lfloor v/m\rfloor=L$，而用最便宜数字可构造 $L$ 位，所以最优答案恰有 $L$ 位。构造某一位时，条件保证选定该数字后仍能补齐剩余位；从 9 向下选出的第一个数字是当前前缀可行的最大选择。按字典序逐位贪心，得到所有 $L$ 位可行整数中字典序最大者，也就是数值最大者。

复杂度分析

时间复杂度 $O(9L)$，输出外空间复杂度 $O(1)$。