FZU 算法设计与分析 5.3 数字排列（数字的字典序算法）

题目描述：

给两个正整数A和B，请问通过重新排列A获得小于或等于B的最大数字是多少(不含前导0)？

输入格式：

输入的第一行两个数字A和B ，保证这两个数字在int范围内。

输出格式：

输出A重新排列后小于或等于B的最大整数(不含前导0)，若不存在输出−1。

样例输入：

1234 3456

样例输出：

3421

思路：

首先把A按字典序从大到小排序，然后一个个试过去，直到第一个小于或等于B的数出现的时候及时刹车就好了。

对于数字1、2、3......n的排列，不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的。例如对于5个数字的排列 12354和12345，排列12345在前，排列12354在后。按照这样的规定，5个数字的所有的排列中最前面的是12345，最后面的是 54321。

说白了就是按从大到小排序而已，然后第一个比B小的数即为结果，附上代码，来自实验室的一位喜欢算法的小伙伴。

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;
int A[10];
int B[10];
int n = 0;
int m = 0;
int a, b;
int x;
int flag = 0;
int sum = 0;

int main()
{
    cin >> a >> b;//输入 

    while (a != 0) {//拆解 
        x = a % 10;
        a = a / 10;
        A[n] = x;
        n++;
    }

    while (b != 0) {//拆解 
        x = b % 10;
        b = b / 10;
        B[m] = x;
        m++;
    }



    if (m < n)
        cout << -1;

 sort(A, A + n, greater<int>());//排序        

    if (m > n) {
        for (int i = 0; i < n; i++)
            sum += A[i] * pow(10, n - i - 1);
        cout << sum;
    }

    else {
        
        do
        {
            
            flag = 1;
            for (int i = 0; i < n; i++) {
                if (A[0] == 0) {
                    flag = 0;
                    break;
                }

                if (A[i] > B[n - i - 1]) {
                    flag = 0;
                    break;
                }

                else if (A[i] < B[n - i - 1])
                    break;

                else
                    ;
            }

            if (flag == 1) {
                for (int i = 0; i < n; i++)
                    sum += A[i] * pow(10, n - i - 1);
                cout << sum;
                break;
            }

        } while (next_permutation(A, A + n, greater<int>()));//全排列 

        if (flag == 0) {
            cout << -1;
        }
    }
}