G2006 [GESP202309 二级] 数字黑洞 题解

知识点：数字处理、排序、模拟。

解题思路

把当前数补足三位，排序得到最小排列，再反转得到最大排列，用两者之差更新，直到495。

为什么正确

每轮完整执行一次题目规定的变换，计数器记录已执行次数；到达目标时结束。

易错点

差小于100时仍要补前导0；输入已是495时答案为0。

复杂度

设迭代次数K，时间O(K)，空间O(1)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,ans=0;
    cin>>n;
    while(n!=495) {
        string s=to_string(n);
        while(s.size()<3)s="0"+s;
        sort(s.begin(),s.end());
        int lo=stoi(s);
        reverse(s.begin(),s.end());
        n=stoi(s)-lo;
        ans++;
    }
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用8个自行生成的测试点。