Beautiful Now

HDU - 6351

 

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? InputThe 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.
OutputFor 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

OJ-ID：
hdu-6531

author：
Caution_X

date of submission：
20191028

tags：
暴力

description modelling：
输入n,k，对n进行k次换位操作
(换位操作：例如1234中1，3换位得到3214或者1234中1和1本身进行换位，得到1234)
输出：完成k次换位操作后得到的最小值和最大值

major steps to solve it：
（1）枚举全排列
（2）对所有的交换方法进行尝试，计算交换次数
（3）如果交换次数小于等于k，更新最大值或最小值

warnings：
（1）换位对象可以是本身
（2）本题不能用的贪心思路：找最大值时每次从后往前选择最大的数和准备交换的较小数交换
例如6299 -> 9396 -> 9936 （实际答案9963）

AC code:【贴别人的AC代码：https://blog.csdn.net/anthony1314/article/details/81480055】

#include<bits/stdc++.h>
using namespace std;
 
int maxx, minn, k, len;
int c[20], sum1[20], sum2[20], p[20];
char ss[20];
 
void update() {
    if(c[p[1]] == 0){
        return;
    }
    for(int i = 1; i <= len; i++){
        sum1[i] = p[i];
    }
    int kk = 0, s = 0;
    for(int i = 1; i <= len; i++){
        s = s * 10 + c[p[i]];
        if(sum1[i] != i){
            for(int j = i+1; j <= len; j++){
                if(sum1[j] == i){
                    swap(sum1[i], sum1[j]);
                    kk++;
                    if(kk > k) return;
                    break;
                }
            }
        }
    }
    if(kk > k){
        return ;
    }
    maxx = max(maxx, s);
    minn = min(minn, s);
}
 
int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        memset(sum1,0,sizeof(sum1));
        memset(sum2,0,sizeof(sum2));
        scanf("%s%d",ss,&k);
        len = strlen(ss);
        for(int i = 0; i < len; i++) {
            c[i+1] = ss[i] - '0';
            sum1[c[i+1]]++;
            sum2[c[i+1]]++;
        }
        if(k >= len-1) {//剪枝 
            for(int i = 1; i <= 9; i++) {
                if(sum1[i]) {
                    printf("%d",i);
                    sum1[i]--;
                    break;
                }
            }
            for(int i = 0; i <= 9; i++) {
                while(sum1[i]) {
                    printf("%d",i);
                    sum1[i]--;
                }
            }
            printf(" ");
            for(int i = 9; i >= 0; i--) {
                while(sum2[i]) {
                    printf("%d",i);
                    sum2[i]--;
                }
            }
            printf("\n");
            continue;
        }
        for(int i = 1; i <= len; i++){
            p[i] = i;
        }
        minn = 2e9, maxx = -1;
        do{
            update();
        }while(next_permutation(p+1,p+len+1));//全排列 
        printf("%d %d\n",minn, maxx);
    }
    return 0;
}