2018暑假多校賽【第五場】【全排列】-Beautiful Now-YZHHHHHHH

Beautiful Now

Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)

Total Submission(s): 1746    Accepted Submission(s): 653

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

題意：

給出一個數字 n，交換次數 k，數 n内的經過k 次交換後，分别得到最小值和最大值。

題解：

要求最小值，那麼盡量讓小的數往前靠就行了，最大值同理。

最容易想到的就是貪心暴力過，但是有些資料會過不了，比如：524111  3

答案應該是：111245  542111

那麼應該咋做呢？

我們發現這道題給得時間挺多的，2500ms，是以我們可以考慮暴力周遊所有情況，

也就是【全排列】，next_permutation(start, end);

對于next_permutation函數，其函數原型為：

     #include <algorithm>

     bool next_permutation(iterator start,iterator end)

當目前序列存在下一個排列時，傳回true,否則傳回false

相對應的有，prev_permutation（start,end）；

利用next_permutation 我們就可以周遊所有的情況

代碼

#include <bits/stdc++.h>
using namespace std;

char s[100];
int k, c[100];
int maxx, minn;
int len;
int p[100], q[100];


void upDate(){
    if (c[p[0]] == 0) return;
    int kk = 0;
    int ss = 0;
    for (int i = 0; i < len; i++) q[i] = p[i];
    
    for (int i = 0; i < len; i++){
        ss = ss*10 + c[p[i]];
        if (q[i] != i){
            for (int j = i+1; j < len; j++){
                if (q[j] == i){
                    swap(q[i], q[j]);
                    kk++;
                    if (kk > k) return;
                    break;
                }
            }
        }
    }
    if (kk > k) return;
    maxx = max(ss, maxx);
    minn = min(ss, minn);
    //printf("-->%d %d  ss->%d\n",minn, maxx, ss);
}

int main() {
    int t;
    scanf("%d",&t);
    getchar();
    while (t--){
        
        scanf("%s %d", s, &k);
        memset(q, 0, sizeof(q));
        memset(p, 0, sizeof(p));
        len = strlen(s);
        // 如果k 大于等于 字元串長度-1，直接輸出最小值和最大值 
        if (k >= len-1){ 
            for (int i = 0; i < len; i++){
                c[i] = s[i]-'0';
                q[c[i]]++;
                p[c[i]]++; 
            }
            
            for (int i = 1; i <= 9; i++){
                if (q[i]){
                    printf("%d",i);
                    q[i]--;
                    break;
                }
            }
            for (int i = 0; i <= 9; i++){
                while (q[i]){
                    printf("%d",i);
                    q[i]--;
                }
            }
            printf(" ");
            for (int i = 9; i >= 0; i--){
                while (p[i]){
                    printf("%d",i);
                    p[i]--;
                }
            }
            printf("\n");
        }
        
        else {
        
            for (int i = 0; i < len; i++){
                c[i] = s[i] - '0';
            }
            
            for (int i = 0; i < len; i++) p[i] = i;
            maxx = -1, minn = 0x3f3f3f3f;
        //    printf("-->%d %d\n", minn, maxx);
            do {
                
                upDate();
            }while (next_permutation(p, p+len));
            printf("%d %d\n", minn, maxx);
        }
        
    }
}