题目分析

本题要求我们对给定的正整数进行一种特定的数字变换，并记录变换过程中形成的“数字链”，直到出现重复的数字为止。变换规则如下：

1. 将当前数字的各位数字按降序排列，得到一个大数 $big$。
2. 将当前数字的各位数字按升序排列，得到一个小数 $small$。
3. 计算差值 $difference=big-small$。
4. 用差值作为新的数字，重复上述步骤，直到新生成的数字已经在之前的链中出现过为止。

需要注意：

• 数字允许包含前导零（例如 $1234$ 的升序排列是 $1234$，降序是 $4321$；而 $3087$ 的升序是 $0378=378$，降序是 $8730$）。
• 输入数字小于 $10^9$，最多有 $5000$ 个数字。
• 每条链的长度定义为链中不同数字的个数。
• 输出格式要求：每个数字链的输出后跟一个空行。

解题思路

1. 问题本质

这个问题的本质是模拟一个确定的数字变换过程，并检测循环。由于每一步变换的结果完全由当前数字的各位数字决定，因此这是一个确定性系统。由于数字范围有限（小于 $10^9$，即最多 $9$ 位），可能的数字状态是有限的，因此必然会进入循环。

2. 算法设计

我们需要对每个输入数字：

1. 输出原始数字（格式要求第一行）。
2. 使用一个集合（set）记录已经出现过的数字。
3. 循环进行变换：
   • 将当前数字转换为字符串，以便对各位数字进行排序。
   • 分别按降序和升序排序得到 $big$ 和 $small$。
   • 计算差值。
   • 输出当前步骤的算式。
   • 检查差值是否已经在集合中：
     • 如果已存在，说明链结束，输出链长度。
     • 否则，将差值加入集合，更新当前数字，链长度加 $1$。

3. 细节处理

3.1 数字与字符串的转换

在 C++ 中，可以使用 to_string 将整数转换为字符串，使用 stoi 将字符串转换为整数。

3.2 排序规则

• 降序排列：按字符从大到小排序，对应较大的数字。
• 升序排列：按字符从小到大排序，对应较小的数字。

注意：升序排列后可能产生前导零（例如 $100$ 的升序是 $001=1$），但 stoi 会自动忽略前导零，因此无需特殊处理。

3.3 链的长度统计

题目要求链的长度是链中不同数字的个数。在我们的算法中，当新生成的差值已经在集合中出现时，我们不将它再次加入集合，此时链的长度 $length$ 已经记录了集合中元素的个数。

3.4 循环终止条件

循环在发现新生成的差值已经在集合中时终止。例如 $444$ 的情况：

• 原始数字 $444$，降序 $444$，升序 $444$，差值为 $0$。
• $0$ 未出现过，继续。
• 下一轮：$0$ 的降序和升序都是 $0$，差值为 $0$，此时 $0$ 已经在集合中，终止。
  这样链的长度为 $2$，与示例输出一致。

4. 复杂度分析

• 每个数字最多变换 $1000$ 次（题目保证）。
• 每次变换需要排序，数字位数最多 $9$，排序复杂度可视为 $O(9\log 9)\approx O(1)$。
• 集合的插入和查找操作平均 $O(\log L)$，其中 $L$ 是当前链长度，$L\le 1000$。
• 总时间复杂度：对于每个输入数字，$O(1000\log 1000)\approx O(10^4)$，对于 $5000$ 个数字完全可行。

代码实现

// Number Chains
// UVa ID: 263
// Verdict: Accepted
// Submission Date: 2016-05-10
// UVa Run Time: 0.380s
//
// 版权所有（C）2016，邱秋。metaphysis # yeah dot net

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

// 降序比较函数，用于将数字的各位从大到小排列
bool cmp1(char x, char y) {
    return x > y;
}

// 升序比较函数，用于将数字的各位从小到大排列
bool cmp2(char x, char y) {
    return x < y;
}

int main() {
    cin.tie(0); cin.sync_with_stdio(false);
    int number;
    // 持续读入数字，直到遇到 0 为止
    while (cin >> number, number) {
        // 输出原始数字，格式要求第一行
        cout << "Original number was " << number << endl;
        int length = 1;                 // 链的长度，初始包含原始数字
        set<int> appeared;              // 记录已经出现过的数字
        while (true) {
            // 将当前数字转为字符串，以便对各位数字排序
            string text = to_string(number);
            // 降序排列得到大数
            sort(text.begin(), text.end(), cmp1);
            int big = stoi(text);
            // 升序排列得到小数
            sort(text.begin(), text.end(), cmp2);
            int small = stoi(text);
            // 计算差值
            int difference = big - small;
            // 输出当前步骤的算式
            cout << big << " - " << small << " = " << difference << endl;
            // 如果差值已经在链中出现过，则链结束
            if (appeared.count(difference) > 0) {
                cout << "Chain length " << length << endl;
                break;
            } else appeared.insert(difference);   // 将新差值加入集合
            number = difference;                // 用差值继续下一轮变换
            length++;                           // 链长度增加
        }
        // 每个数字链输出后跟一个空行
        cout << endl;
    }
    return 0;
}

总结

本题是一个简单的模拟题，核心在于正确实现数字各位的排序与差值计算，并利用集合检测循环。代码结构清晰，使用 set 记录历史数字，避免了复杂的循环检测逻辑。注意输出格式中的空行要求，以及链长度的正确计算方式。通过本题可以熟悉 C++ 中字符串与整数的转换、排序函数以及集合的使用。