题解

题目解析

• 输入输出：输入一个各位数字互不相同的三位数 $N$；输出经过多少次变换（重排求差）后得到 $495$。
• 数据范围：三位数且各位不同，即 $102 \leq N \leq 987$（不含重复数字）。
• 复杂度要求：时间复杂度 $O(C \cdot \log d)$，其中 $C$ 为变换次数（实验表明 $C \leq 6$ 即可收敛），$d=3$ 为数字位数；空间复杂度 $O(1)$。
• 算法知识点：模拟、字符串处理、排序、数字重排

思路解析

1. 循环模拟变换：以 $N = 495$ 为终止条件，每次循环执行一次重排求差操作，并用计数器统计次数。
2. 构造最大与最小数：将当前数字转为字符串后，利用 sort 得到升序排列（对应最小数的数字顺序），再 reverse 得到降序排列（对应最大数的数字顺序）。通过 stoi 转回整数后相减，即得新数字。
3. 收敛性保证：数学上，任意无重复数字的三位数经过有限次“重排求差”操作必收敛于 $495$（Kaprekar 常数），因此无需处理无限循环。

完整代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int cnt = 0;
    
    // 模拟变换过程，直到达到数字黑洞 495
    while (n != 495) {
        // 将数字转为字符串便于排序
        string s = to_string(n);
        // 升序排列：得到最小数的数字排列（如 297 -> "279"）
        sort(s.begin(), s.end());
        // 降序排列：复制后反转得到最大数（如 297 -> "972"）
        string res = s;
        reverse(res.begin(), res.end());
        
        // 计算差值作为下一次迭代的数字
        n = stoi(res) - stoi(s);
        cnt++;
    }
    
    cout << cnt << endl;
    return 0;
}