交换一个数字的任意两个位置,指定K次的最值

时间:2020-12-11 10:31:25

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 (x1x2xm)10 satisfying that 1x19, 0xi9 (2im), which means n=mi=1xi10mi. In each swap, Anton can select two digits xi and xj (1ijm) 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.
1T100, 1n,k109.
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
题意 : 给你一个数字,可以交换任意两个位置,求交换K 次后的最大以及最小值
思路分析 : 比赛的时候写了个贪心,.... 各种试数据,试一组,WA一次,赛后写了个广搜,过了
代码示例 :
int n, k;
char s[50], f[50];
int len;
struct node
{
    string str;
    int pos, num;    
};
queue<node>que;

int cal(string str) {
    int res = 0;
    for(int i = 0; i < len; i++) res = res*10+(str[i]-'0');
    return res;
}

void bfs1() {
    while(!que.empty()) que.pop();
    que.push({s+1, 0, 0});
    int ans = inf;
    
    while(!que.empty()){
        node v = que.front(); que.pop();
        int p = v.pos;
        if (v.num <= k) ans = min(ans, cal(v.str));
        if (p >= len) break;
        if (v.num > k) continue;
        int mmin = 1000;
        for(int i = p+1; i < len; i++) {
            if (p == 0 && v.str[i] == '0') continue;
            mmin = min(mmin, v.str[i]-'0');
        }
        if (mmin >= (v.str[p]-'0')){
            que.push({v.str, p+1, v.num});
            continue;
        }
        int sign = 0;
        for(int j = len-1; j > p; j--){
            sign = 1;
            if ((v.str[j]-'0') == mmin) {
                swap(v.str[j], v.str[p]);
                que.push({v.str, p+1, v.num+1});
                swap(v.str[j], v.str[p]);
            }
        }
        if (!sign) que.push({v.str, p+1, v.num});
    }
    cout << ans << " ";
}

void bfs2(){    
    //swap()
    while(!que.empty()) que.pop();
    que.push({s+1, 0, 0});
    int ans = -1;
    
    while(!que.empty()) {
        node v = que.front(); que.pop();
        int p = v.pos;
        if (v.num <= k) ans = max(ans, cal(v.str));
        if (p >= len) break;
        if (v.num > k) continue;
        int mmax = -1;
        for(int i = p+1; i < len; i++) mmax = max(mmax, v.str[i]-'0');
        if (mmax <= (v.str[p]-'0')) {
            que.push({v.str, p+1, v.num});
            continue;
        } 
        int sign = 0;
        for(int j = len-1; j > p; j--){
            sign = 1;
            if ((v.str[j]-'0') == mmax) {
                swap(v.str[j], v.str[p]);
                que.push({v.str, p+1, v.num+1});
                swap(v.str[j], v.str[p]);
            }
        }
        if (!sign) que.push({v.str, p+1, v.num});
    }
    cout << ans << endl;
}

int main() {
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    int t;
    
    cin >> t;
    while(t--){
        scanf("%s%d", s+1, &k);
        len = strlen(s+1);
        bfs1();
        bfs2();
    }
    return 0;
}