19.5 构造最大数和最小数

“现在让我们学习如何用给定的数字构造最大数和最小数，”我说道，”这需要巧妙地运用排序！”

19.5.1 n个一位数能够组成的最大数和最小数

题目描述： 请问n个一位数能够组成的最大的整数和最小的整数是多少。比如，n=3，3个整数为1、3、9，那么组成的最大整数是931，最小数是139。比如，n=4，4个整数为2、8、0、6，那么组成的最大整数是8620，最小数是2068。

输入格式： 第一行为一个整数n（n<10）。第二行为n个一位数。

输出格式： 第一行输出最大整数，第二行输出最小整数。

样例：

• 输入：4 7 3 4 4 输出：7443 3447

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

int main(){
    int a[15];
    int n;
    cin >> n;
    
    // 输入n个一位数
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    
    // 对数组进行升序排序
    sort(a+1, a+1+n);
    
    // 构造最大数：从大到小取数字
    int m = 0;
    for(int i = n; i >= 1; i--){
        m = m * 10 + a[i];  // 将数字逐位组合
    }
    cout << m << endl;
    
    // 构造最小数：处理前导零问题
    int k = 1;
    while(a[k] == 0) k++;  // 找到第一个非零数字
    swap(a[1], a[k]);      // 与第一位交换，避免前导零
    
    m = 0;
    for(int i = 1; i <= n; i++){
        m = m * 10 + a[i];  // 重新组合成最小数
    }
    cout << m;
    
    return 0;
} 

算法解析：

1. 先对数组升序排序
2. 最大数：从排序后的末尾开始取数字，逐位构造
3. 最小数：从排序后的开头取数字，但需处理前导零
4. 如果首位是0，与第一个非零数字交换位置
5. 使用数学方法m = m × 10 + digit组合数字