位数之和等于x的n

一次笔试的题目，题目原表述和空间要求等已经记不清，凭回忆和草稿恢复题目如下：

输入 $T$ 组数，格式为第 1 行是组数 $T$ ，余下每行 1 个数 $x$ ，对每个 $x$ 求输出对应的 $n$ ，满足 $x \leq S(n)$ 的最小值。其中 $S(n)$ 表示 $n$ 的十进制各位之和， $1 \leq T \leq 10$, $1 \leq x \leq 10^5$。

示例输入

2

13

18

示例输出

49

99

Java实现

import java.util.Scanner;

public class Exam1 {

    public static void main(String[] args) {

        Scanner stdIn = new Scanner(System.in);
        int T; // 组数

        do {
            System.out.print("请输入数据组数T(1 <= T <= 10)：");
            T = stdIn.nextInt();
        } while (T < 1 || T > 10);

        int[] x = new int[T]; // 输入的x

        for (int i = 0; i < T; i++) {
            do {
                System.out.printf("请输入第%2d 组的 x(1 <= x <= 100000)：", (i + 1));
                x[i] = stdIn.nextInt();
            } while (x[i] < 1 || x[i] > 100000);
        }
        stdIn.close();
        for (int number : x) {
            System.out.print((number % 9 == 0) ? "" : (number % 9));
            for (int i = 0; i < number / 9; i++) {
                System.out.print(9);
            }
            System.out.println();
        }
    }
}

思考过程

考试的时候初步想法，输入数据组数 $T$ ，接下来每组的数保存在长度为 $T$ 的整型数组里面。 这只是输入数据的保存，接着就是核心算法部分，思考这个算法要做什么，要寻找什么规律，最终达到题目要求。

我是这样想的，首先实现对于每个 $x$ 可以找到满足条件的 $n$ ，接着再考虑怎么知道这个 $n$ 是最小的，判断的依据是什么？功能实现完善了，再考虑优化时间复杂度或空间复杂度。

初步来看，随着 $x$ 增大，符合条件的 $n$ 将会是一个很大的数，位数肯定超过 Java 支持的数据类型上限，这就是要考虑到的问题。 但可以先从小数入手，先实现在 $x$ 较小的情况下可以运行的程序，接着优化，添加可以处理大数的操作，使得在题目要求的数值范围内可以有效运行。最后才是细化优化。

后来观察了一下这些数字，发现规律很明显，不用很复杂的算法就可以实现了。首先题目要求对于给定的 $x$ 要找到满足 $x \leq S(n)$ 的 $n$ 的最小值，所以最小就是 $x = S(n)$ 的情形。列出一些 $x$ 和 对应的 $n$ 如下：

1 … 8 9 10 11 12 … 28

1 … 8 9 19 29 39 … 1999

发现满足要求的都是最高位是 1~8 其余位数全部是 9 的数字（不然不可能最小）。所以问题就转化成求 $n$ 的最高位是什么，余下位数共有多少个 9 ，即最高位是 $n$ % 9, 余下有 $n$ / 9 个 9。 因为 $x = 10^5$ 的时候，满足条件的 $n$ 长度是 “最高位的 1 ” + “ 后面11111 个 9 ”， 长度达到 11112 位。 因此用打印字符串作为结果输出。时间复杂度$O(n)$。

总结

这题和轮流取硬币的那题都涉及到余数相关的性质，感觉有趣，平时解题思维锻炼得少，有时候会将简单问题复杂化，要多练习，希望有提高。