P4659 整数重组（基础）

解题思路

第一步，读懂题目。 给一个正整数，把它的每一位数字重新排列，组成一个最大的数和一个最小的数，然后求出两数的差。比如 3721：把 7、3、2、1 从大到小排成 7321 就是最大数，从小到大排成 1237 就是最小数，差是 7321-1237=6084，和样例一致。

第二步，最大数很简单。 把数字从大到小排列即可。先把数字字符存进数组，用 sort 从小到大排好后，再倒过来读就是最大数。

第三步，最小数要小心"前导零"。 比如数字 102，三个数字从小到大排是 012，如果直接把它当数就是 12，但用 1、0、2 这三个数字组成的最小数其实是 102。正确的做法是：先把数字从小到大排好，找到第一个不是 0 的数字，把它放到最前面，剩下的数字再按从小到大排。比如 4050，从小到大排是 0045，最小的非 0 数字是 4，把它放最前面，剩下 0、0、5 排成 005，最小数就是 4005，最大数是 5400，差是 1395。

第四步，用大数减法算差。 如果数字位数很多，直接转成整数可能超出范围，所以我们把最大数和最小数都当作字符串，从个位开始一位一位相减，不够减就向高一位借 1（借 1 当 10），最后把结果前面多余的 0 去掉再输出。这样无论位数再多都不会溢出。

第五步，处理位数不齐的情况。 如果最大数和最小数的位数不一样（比如最小数因为去掉前导零而变短），减法时我们按最长的位数对齐，短的那一位不足就当作 0 处理，这样计算不会出错。再完整走一遍示例 3721：数字排序后是 1237，最大数是 7321，最小数是 1237，相减得到 6084，正好是样例输出。想清楚"前导零"这一步，整道题就迎刃而解了。

参考代码

// P4659 整数重组：把数字重排成最大值和最小值，求两者之差（大数减法防溢出）
#include <iostream>
#include <algorithm>
using namespace std;

char digitStr[50], maxNum[50], minNum[50], result[50];

int main() {
    cin >> digitStr;
    int length = 0;
    while (digitStr[length] != '\0') length++;
    sort(digitStr, digitStr + length); // 数字字符从小到大排序
    // 最大值：倒序排列
    for (int i = 0; i < length; i++) maxNum[i] = digitStr[length - 1 - i];
    maxNum[length] = '\0';
    // 最小值：把最小的非 0 数字放最前面（避免前导 0），再排剩余数字
    int first = 0;
    while (first < length && digitStr[first] == '0') first++;
    int minLen;
    if (first == length) {              // 所有位都是 0
        minNum[0] = '0';
        minNum[1] = '\0';
        minLen = 1;
    } else {
        int writeIdx = 0;
        minNum[writeIdx++] = digitStr[first];
        for (int i = 0; i < length; i++)
            if (i != first) minNum[writeIdx++] = digitStr[i];
        minNum[writeIdx] = '\0';
        minLen = writeIdx;
    }
    // 大数减法：maxNum - minNum
    int borrow = 0, resIdx = 0, maxIdx = length - 1, minIdx = minLen - 1;
    while (maxIdx >= 0 || minIdx >= 0) {
        int a = (maxIdx >= 0) ? maxNum[maxIdx] - '0' : 0;
        int b = (minIdx >= 0) ? minNum[minIdx] - '0' : 0;
        a -= borrow;
        if (a < b) {
            a += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        result[resIdx++] = (char)(a - b + '0');
        maxIdx--;
        minIdx--;
    }
    // 去掉结果前导 0 后输出
    int startIdx = resIdx - 1;
    while (startIdx > 0 && result[startIdx] == '0') startIdx--;
    for (int i = startIdx; i >= 0; i--) cout << result[i];
    cout << endl;
    return 0;
}

复杂度分析

设数字有 d 位：排序需要 O(d log d)，构造最大数和最小数需要 O(d)，大数减法也是 O(d)。d 通常很小，所以整体非常快。空间上只用了几个长度为 d 的字符数组，O(d)。