Beautiful Now

Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0

Problem Description

Anton has a positive integer n, however, it quite looks like a mess, so he wants to make it beautiful after k swaps of digits.
Let the decimal representation of n as (x1x2⋯xm)10 satisfying that 1≤x1≤9, 0≤xi≤9 (2≤i≤m), which means n=∑mi=1xi10m−i. In each swap, Anton can select two digits xi and xj (1≤i≤j≤m) and then swap them if the integer after this swap has no leading zero.
Could you please tell him the minimum integer and the maximum integer he can obtain after k swaps?

Input

The first line contains one integer T, indicating the number of test cases.
Each of the following T lines describes a test case and contains two space-separated integers n and k.
1≤T≤100, 1≤n,k≤109.

Output

For each test case, print in one line the minimum integer and the maximum integer which are separated by one space.

Sample Input

5
12 1
213 2
998244353 1
998244353 2
998244353 3

Sample Output

12 21
123 321
298944353 998544323
238944359 998544332
233944859 998544332

枚举每种交换情况，分别取最大和去最小，记得特判前导零

AC代码：

#include <map>

#include <set>

#include <stack>

#include <cmath>

#include <queue>

#include <cstdio>

#include <vector>

#include <string>

#include <bitset>

#include <cstring>

#include <iomanip>

#include <iostream>

#include <algorithm>

#define ls (r<<1)

#define rs (r<<1|1)

#define debug(a) cout << #a << " " << a << endl

using namespace std;

typedef long long ll;

const ll maxn = 1e2+10;

const ll mod = 998244353;

const double pi = acos(-1.0);

ll n, m;

bool cmp( char p, char q ) {

    return p > q;

}

string strmin, strmax, s, tmin, tmax;

void dfs1( ll x, ll cnt, string t ) {

    if( cnt > n-1 || x == t.length()-1 ) {

        //debug(cnt), debug(tmin), debug(strmin), debug(t);

        strmin = min(strmin,t);

        return ;

    }

    if( t[x] == tmin[x] ) {

        dfs1(x+1,cnt,t);

        return ;

    }

    char c = 'a';

    for( ll i = x+1; i < t.length(); i ++ ) {

        if( t[i] <= c ) {

            if( x == 0 && t[i] == '0' ) {

                continue;

            }

            c = t[i];

        }

    }

    if( c == 'a' ) {

        dfs1(x+1,cnt,t);

        return ;

    }

    for( ll i = x+1; i < t.length(); i ++ ) {

        if( t[i] == c ) {

            swap(t[i],t[x]);

            dfs1(x+1,cnt+1,t);

            swap(t[i],t[x]);

        }

    }

}

void dfs2( ll x, ll cnt, string t ) {

    if( cnt > n-1 || x == t.length()-1 ) {

        //debug(cnt), debug(tmax), debug(strmax), debug(t);

        strmax = max(strmax,t);

        return ;

    }

    if( t[x] == tmax[x] ) {

        dfs2(x+1,cnt,t);

        return ;

    }

    char c = '0';

    bool flag = true;

    for( ll i = x+1; i < t.length(); i ++ ) {

        if( t[i] >= c ) {

            c = t[i];

            flag = false;

        }

    }

    for( ll i = x+1; i < t.length(); i ++ ) {

        if( t[i] == c ) {

            swap(t[i],t[x]);

            dfs2(x+1,cnt+1,t);

            swap(t[i],t[x]);

        }

    }

}

string rev( string s ) {

    string t = "";

    for( ll i = 0, j = s.length()-1; i < s.length(); i ++, j -- ) {

        t = t + s[j];

    }

    return t;

}

int main() {

    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	ll T, t = 1;

	cin >> T;

	while( T -- ) {

        s = "";

        ll j = 0;

        cin >> m >> n;

        while(m) {

            char c = (m%10)+'0';

            s = s + c;

            m /= 10;

        }

        s = rev(s);

        tmin = s, tmax = s;

        sort(tmin.begin(),tmin.end());

        sort(tmax.begin(),tmax.end(),cmp);

        if( tmin[0] == '0' ) {

            char c = 'a';

            ll inx = -1;

            for( ll i = 1; i < tmin.length(); i ++ ) {

                if( tmin[i] != '0' && tmin[i] < c ) {

                    c = tmin[i];

                    inx = i;

                }

            }

            if( inx != -1 ) {

                swap(tmin[inx],tmin[0]);

            }

        }

        if( n >= s.length()-1 ) {

            cout << tmin << " " << tmax << endl;

        } else {

            strmin = s;

            dfs1(0,0,strmin);

            strmax = s;

            dfs2(0,0,strmax);

            cout << strmin << " " << strmax << endl;

        }

	}

	return 0;

}

/*

123112 2

111322 322111

10001 2

*/

巴特西

hdu6351 Beautiful Now 杭电第五场暴力枚举

Beautiful Now

最新文章

热门文章

巴特西

hdu6351 Beautiful Now 杭电第五场 暴力枚举

Beautiful Now

最新文章

热门文章

hdu6351 Beautiful Now 杭电第五场暴力枚举