19.2 数字重新排列

“接下来，让我们学习一个有趣的应用——如何重新排列数字的各位，得到最小的数！”我继续说道。

19.2.1 重新排列获得最小数

题目描述： 现在有一个30位以内的自然数，你可以将组成这个数的各位数字重新排列，得到一个数值为最小的新数，但新数的位数保持不变。请编程打印出重新排列后的新数。（如：231重新排序后位数不变的最小数是123，而23105重新排序后位数不变的最小数是10235）

输入格式： 一个整数（位数≤30位）。

输出格式： 重新排列后最小的新数。

样例：

• 输入：382 输出：238
• 输入：231050 输出：100235

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

int main(){
    string s;
    cin >> s;  // 以字符串形式读入，避免大数问题
    
    // 对所有字符进行升序排序
    sort(s.begin(), s.end());
    
    // 处理前导零：找到第一个非零字符的位置
    int k = 0;
    while(s != "0" && s[k] == '0') k++;
    
    // 将第一个非零字符与首位交换，避免前导零
    swap(s[0], s[k]);
    
    cout << s;
    return 0;
} 

算法解析：

1. 使用字符串读入，避免30位大数的溢出问题
2. 对字符串进行升序排序，得到字典序最小的排列
3. 特殊处理：如果首位是’0’，需要找到第一个非’0’字符与之交换
4. 这样既保证了数值最小，又避免了前导零的问题