codeforces 915 C(思维+模拟)

C. Permute Digits time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

You are given two positive integer numbers a and b. Permute (change order) of the digits of a to construct maximal number not exceeding b. No number in input and/or output can start with the digit 0.

It is allowed to leave a as it is.

Input

The first line contains integer a (1 ≤ a ≤ 1018). The second line contains integer b (1 ≤ b ≤ 1018). Numbers don‘t have leading zeroes. It is guaranteed that answer exists.

Output

Print the maximum possible number that is a permutation of digits of a and is not greater than b. The answer can‘t have any leading zeroes. It is guaranteed that the answer exists.

The number in the output should have exactly the same length as number a. It should be a permutation of digits of a.

Examples input Copy

123
222

output Copy

213

input Copy

3921
10000

output Copy

9321

input Copy

4940
5000

output Copy

4940

 题意：给你两个整数a，b。让你把组成a的数字排列后成比b小的最大的数字。

思路：最开始想，从b的最高位（最左面的数）遍历，从a中找相等的数，当找到的没有相等，而是小于，则把a中没有输出的数从大到小输出（反解：98 ，91）

　　　　后来想dfs跑，但是会超时（例如200000001，200000000））

正解:把a，b拆出来到数组中，把a从大到小排序。从b的最高位（最左面的数）遍历，从a中找相等的数，当找到相等则取，如果没有相等的情况还存在两种情况，只存在大于的b[i]的数，和只存在小于b[i]的数

　　　　如果后者，则把a中没有输出的数从大到小输出。如果存在前者，则回溯（i -=  2），直到找到一个可以找到有比b[i]（这个i和前面的i不同），然后把a中没有输出的数从大到小输出即可。

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <map>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <vector>
//const int maxn = 1e5+5;
#define ll long long
#define inf 0x3f
#define FOR(i,a,b) for( int i = a;i <= b;++i)
#define bug cout<<"--------------"<<endl
#define bugs cout<<"SSSSSSSSSSSSSSS"<<endl

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
const int maxn = 5100;
using namespace std;
int a[50],b[50],vis[50],cun[50];
int t[50];
int tail1,tail2;

int n;
int findsame(int k)
{
    for(int i = 1;i <= n; ++i)
    {
        if(a[i] == b[k] && vis[i] == 0) return i;
    }
    return 0;
}
int findsmall(int k)
{
    for(int i = 1;i <= n; ++i)
    {
        if(a[i] < b[k] && vis[i] == 0) return i;
    }
    return 0;
}
int main()
{
    
    //freopen("C:\\ACM\\input.txt","r",stdin);
    ll x,y;
    cin>>x>>y;
     tail1 = 0;
     tail2 = 0;
    while(x)
    {
        a[++tail1] = x % 10;
        x /= 10;
    }
    while(y)
    {
        b[++tail2] = y % 10;
        y /= 10;
    }    
    sort(a+1,a+tail1+1);
    reverse(a+1,a+1+tail1);
    reverse(b+1,b+1+tail2);

    if(tail1 < tail2 )
    {
        for(int i = 1;i <= tail1; ++i)
            cout<<a[i];
    }
    else 
    {
        n = tail1;
        int flag = 0;
        int Head = 0;
        stack<int>sta;
        for(int i = 1;i <= n; ++i)
        {

            if(flag == 1)
            {
                int temp = sta.top();sta.pop();
                vis[temp] = 0;
                if(findsmall(i) != 0)
                {
                    
                    cun[i] = a[findsmall(i)];
                    Head = i;
                    vis[findsmall(i)] = 1;
                    break;
                } 
                else i-=2;
                continue;
            }
            if(findsame(i) != 0)
            {
                cun[i] = a[findsame(i)];
                sta.push(findsame(i));
                //cout<<findsame(i)<<endl;
                
                vis[findsame(i)] = 1; 
                
                
            }
            else if(findsmall(i) != 0)
            {
                cun[i] = a[findsmall(i)];
                sta.push(findsmall(i));


                Head = i ;
                vis[findsmall(i)] = 1;
                
                break;
            }
            else 
            {
                i -= 2;
                flag = 1;
            }
            if(i == n) Head = n;
        }


/*        for(int i = 1;i <= n; ++i) cout<<vis[i]<<" ";
        cout<<endl;
        bug;*/
        for(int i = 1;i <= Head; ++i) cout<<cun[i]; 
        for(int i = 1;i <= n; ++i) if(vis[i] ==0) cout<<a[i];

    }
}