Beautiful Now Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others) Total Submission(s): 1110 Accepted Submission(s): 394
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
题意：任意交换两个数，问交换k次后得到的最大值和最小值。 做法：枚举最左边不是最小的数字，然后枚举右边的最小值的位置，每个都交换一下，就可以了， emmm，现场的时候找不到反例就gg了。
#include<bits/stdc++.h> using namespace std; char st[10]; int qp[10]; int n; int ret =0; int get(char *nn){ int su = 0; for(int i = 0;i < n;i ++){ //cout << i << ' '<< nn[i] << ' '<< qp[n-i-1] << endl; su += (nn[i]-'0')*(qp[n-i-1]); } return su; } void cg(char *nn,int mn){ for(int i = n-1;i >= 0;i --){ nn[i]= mn%10+'0'; mn /= 10; } } void dfs(int k){ ret = min(ret,get(st)); if(k == 0){ return ; } for(int i = 0;i < n;i ++){ bool tmp = false; char mn = st[i]; char mn2 = st[i]; for(int j = i+1;j < n;j ++){ mn = min(mn,st[j]); if(st[j]!='0') mn2 = min(mn2,st[j]); } if(i == 0) mn = mn2; if(mn == st[i]) continue; for(int j = i+1;j < n;j ++){ if(st[j] == mn){ tmp = true; swap(st[j],st[i]); dfs(k-1); swap(st[j],st[i]); } } return; } } void dfs2(int k){ ret = max(ret,get(st)); if(k == 0){ return ; } for(int i = 0;i < n;i ++){ char mn = st[i]; for(int j= i+1;j < n;j ++) mn = max(mn,st[j]); if(mn == st[i]) continue; for(int j = i+1;j < n;j ++){ if(st[j] == mn){ swap(st[j],st[i]); dfs2(k-1); swap(st[j],st[i]); } } ret = max(ret,get(st)); return; } } int main(){ qp[0] = 1; for(int i = 1;i < 10;i ++) qp[i] = qp[i-1]*10; int T; cin >> T; while(T--){ int k; scanf("%s %d",st,&k); n = strlen(st); int tmp = get(st); ret = tmp; dfs(min(k,9)); printf("%d ",ret); ret = tmp; //cout << st << endl; dfs2(min(k,9)); printf("%d\n",ret); } return 0; }