codeforces 915C. Permute Digits

矫情吗；* 2022-05-09 16:42 194阅读 0赞

题目链接：[http://codeforces.com/problemset/problem/915/C][http_codeforces.com_problemset_problem_915_C]

C. Permute Digits

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*.

很容易会想a的全排列，但是18！肯定是不行的。

然后就会想统计a中0-9各有几个，然后构造b，但是这样要考虑的太多了，也不可行。

就可以用以下方法啦，先考虑长度，如果b比a长，那直接取a得最大值；否则就考虑a的每一位，先把a从小到大排好，然后用最大值去和a的当前i位换，i位之后的从小到大排（因为此时我只要保证i位换了之后是可行的），记得用c记录一下没换过的a，这样如果换是不可行的，还能把a换回去。

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    #include<iostream>
    #include<string>
    #include<algorithm>
    #include<map>
    #include<set>
    #include<queue>
    #include<vector>
    using namespace std;
    #define inf 0x3f3f3f3f
    #define LL long long
    int main()
    {
    	string a,b,c;
    	cin>>a>>b;
    	sort(a.begin(),a.end());
    	if(a.length()<b.length())
    	{
    		reverse(a.begin(),a.end());	
    		cout<<a<<endl;
    	}
    	else
    	{
    		for(int i=0;i<a.length();i++)
    		{
    			for(int j=a.length()-1;j>i;j--)
    			{
    				c=a;
    				swap(a[i],a[j]);
    				sort(a.begin()+i+1,a.end());
    				if(a>b)
    				{
    					a=c;
    				}
    				else
    				break;
    			}
    		}
    		cout<<a<<endl;
    	}
    }

[http_codeforces.com_problemset_problem_915_C]: http://codeforces.com/problemset/problem/915/C