12949.数字黑洞

题目分析

本题要求计算一个三位数经过多少次“数字黑洞”变换后变为 495。所谓“数字黑洞”变换，是指：

• 将当前三位数的各位数字重新排列，得到能组成的最大数和最小数；
• 用最大数减去最小数，得到的差作为新的三位数（若差不足三位，则用 0 补齐成三位，不过题目中各位数字不全相同保证了差不会出现 0 和不足三位的情况）；
• 重复这一过程，最终必然会稳定在 495。

题目保证输入的三位数各位不全相同，因此变换过程一定会在有限步内到达 495，不会出现死循环。

解题思路

直接按照题目描述的变换过程进行模拟即可：

1. 读入初始三位数 $N$，设置计数器 $C=0$。
2. 判断当前数是否为 495：
   • 若是，则输出当前的计数器值 $C$，结束；
   • 否则，将当前数的三个数字分解出来，排序得到最大数和最小数，计算差值，计数器加 $1$，用差值替换当前数，回到步骤 2。

由于各位不全相同的三位数至多变换几次就会到达 495，因此直接模拟是可行的。

算法说明

参考代码中使用了一种直接比较的方法来构造最大数和最小数。具体步骤如下：

1. 提取当前数 $n$ 的个位 m0、十位 m1、百位 m2。
2. 通过 if-else 分支判断三个数字的大小顺序（共 6 种情况），直接写出对应的最大数和最小数：
   • 例如，当 $m0 \ge m1 \ge m2$ 时，最大数为 $m0 \times 100 + m1 \times 10 + m2$，最小数为 $m2 \times 100 + m1 \times 10 + m0$；
   • 同理处理其他 5 种排列情况。
3. 令 $n = t_{max} - t_{min}$，完成一次变换，变换次数加 1。

这种写法虽然分支较多，但对于三个数字而言非常直观，完全避免了排序函数的调用，执行效率很高。

更简洁的实现也可以使用数组存储三个数字，调用 sort 进行排序后再构造最大数与最小数，但在竞赛中直接分类讨论也是常见且高效的做法。

参考代码

cpp
复制
1#include <iostream>
2using namespace std;
3
4int main() {
5    int n = 0;
6    cin >> n;
7    
8    for (int t = 0; ; t++) {
9        // 如果已经达到 495，则输出变换次数并结束
10        if (n == 495) {
11            cout << t << endl;
12            break;
13        }
14
15        // 提取三个数字
16        int m0 = n % 10;           // 个位
17        int m1 = n / 10 % 10;      // 十位
18        int m2 = n / 100;          // 百位
19
20        int tmax = 0, tmin = 0;
21
22        // 根据三个数字的大小关系直接构造最大数和最小数
23        if (m0 >= m1 && m1 >= m2) {
24            tmax = m0 * 100 + m1 * 10 + m2;
25            tmin = m2 * 100 + m1 * 10 + m0;
26        } else if (m0 >= m2 && m2 >= m1) {
27            tmax = m0 * 100 + m2 * 10 + m1;
28            tmin = m1 * 100 + m2 * 10 + m0;
29        } else if (m1 >= m0 && m0 >= m2) {
30            tmax = m1 * 100 + m0 * 10 + m2;
31            tmin = m2 * 100 + m0 * 10 + m1;
32        } else if (m1 >= m2 && m2 >= m0) {
33            tmax = m1 * 100 + m2 * 10 + m0;
34            tmin = m0 * 100 + m2 * 10 + m1;
35        } else if (m2 >= m0 && m0 >= m1) {
36            tmax = m2 * 100 + m0 * 10 + m1;
37            tmin = m1 * 100 + m0 * 10 + m2;
38        } else { // m2 >= m1 && m1 >= m0
39            tmax = m2 * 100 + m1 * 10 + m0;
40            tmin = m0 * 100 + m1 * 10 + m2;
41        }
42
43        // 进行一次变换
44        n = tmax - tmin;
45    }
46
47    return 0;
48}

代码解释

• 变量 n 存储当前数字，t 记录已经完成的变换次数。
• 循环开始时先判断 n 是否等于 495，若是则直接输出 t 并退出。
• 提取三个数字：个位 m0，十位 m1，百位 m2。
• 通过穷举 6 种大小顺序，直接构造出由这三个数字组成的最大三位数 tmax 和最小三位数 tmin。
• 用 n = tmax - tmin 更新当前数，进入下一次循环（t 在 for 循环的增量部分自动加 1）。

注意：如果输入的数本身就是 495，循环会在 $t=0$ 时立刻输出 0，符合题意（不需要变换）。

时间复杂度分析

对于任意一个符合要求的初始三位数，循环最多执行 7 次左右即可到达 495（实际上整个过程收敛非常快）。每一次循环只进行常数次数字提取、比较和四则运算。因此整体时间复杂度为 $O(1)$，在任何输入下都能瞬间完成。空间复杂度同样为 $O(1)$。