如何用思维模拟解决codeforces 915 C题？

本文共计995个文字，预计阅读时间需要4分钟。

题目：C. 数字排列

时间限制：每题1秒内存限制：每题256兆字节

输入：标准输入输出：标准输出

描述：给定两个正整数a和b。将a的数字进行排列（改变顺序），以构造出尽可能大的数。

示例：输入：

1234

输出：

4321

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 numbersaandb. Permute (change order) of the digits ofato construct maximal number not exceedingb. No number in input and/or output can start with the digit0.

It is allowed to leaveaas it is.

Input

The first line contains integera(1 ≤ a ≤ 1018). The second line contains integerb(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 ofaand is not greater thanb. 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 numbera. It should be a permutation of digits ofa.

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]; } }