C - Beautiful Now

Anton has a positive integer 

nn, however, it quite looks like a mess, so he wants to make it beautiful after kk swaps of digits. 

Let the decimal representation of nn as (x1x2⋯xm)10(x1x2⋯xm)10 satisfying that 1≤x1≤91≤x1≤9, 0≤xi≤90≤xi≤9 (2≤i≤m)(2≤i≤m), which means n=∑mi=1xi10m−in=∑i=1mxi10m−i. In each swap, Anton can select two digits xixi and xjxj (1≤i≤j≤m)(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 kk swaps?

5
12 1
213 2
998244353 1
998244353 2
998244353 3      

12 21
123 321
298944353 998544323
238944359 998544332
233944859 998544332

      

1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 
  6 using namespace std;
  7 
  8 int maxx,minn,k,len;
  9 int c[20],sum1[20],sum2[20],p[20];
 10 char ss[20];
 11 
 12 void update()
 13 {
 14     if(c[ p[1] ]==0)
 15     {
 16         return;
 17     }
 18     // 用sum1記錄目前排列
 19     for(int i=1;i<=len;++i)
 20     {
 21         sum1[i]=p[i];
 22     }
 23 
 24     int kk=0,s=0;
 25     for(int i=1;i<=len;++i)
 26     {
 27         s=s*10 + c[ p[i] ];
 28         if(sum1[i] != i)
 29         {
 30             for(int j=i+1;j<=len;++j)
 31             {
 32                 if(sum1[j]==i)
 33                 {
 34                     swap(sum1[i],sum1[j]);
 35                     ++ kk;
 36                     // 這一序列不能在k步内實作
 37                     if(kk>k)
 38                     {
 39                         return;
 40                     }
 41                     break;
 42                 }
 43             }
 44         }
 45     }
 46 
 47     // 目前隊列滿足條件
 48     // 更新最大最小值
 49     maxx=max(maxx,s);
 50     minn=min(minn,s);
 51 }
 52 
 53 int main()
 54 {
 55     int T;
 56     scanf("%d",&T);
 57     while(T--)
 58     {
 59         memset(sum1,0,sizeof(sum1));
 60         memset(sum2,0,sizeof(sum2));
 61         scanf("%s %d",ss,&k);
 62 
 63         len=strlen(ss);
 64 
 65         for(int i=0;i<len;++i)
 66         {
 67             // 字元轉數字
 68             c[i+1]=ss[i]-'0';
 69             ++ sum1[ c[i+1] ];
 70             ++ sum2[ c[i+1] ];
 71         }
 72 
 73         // 剪枝
 74         if(k>=len-1)
 75         {
 76             // 輸出最小數
 77             // 輸出第一位（特判非零）
 78             for(int i=1;i<=9;++i)
 79             {
 80                 if(sum1[i])
 81                 {
 82                     printf("%d",i);
 83                     -- sum1[i];
 84                     break;
 85                 }
 86             }
 87 
 88             for(int i=0;i<=9;++i)
 89             {
 90                 while(sum1[i])
 91                 {
 92                     printf("%d",i);
 93                     --sum1[i];
 94                 }
 95             }
 96 
 97             printf(" ");
 98 
 99             // 輸出最大數
100             for(int i=9;i>=0;--i)
101             {
102                 while(sum2[i])
103                 {
104                     printf("%d",i);
105                     -- sum2[i];
106                 }
107             }
108             printf("\n");
109             continue;
110         }
111 
112         // 未能剪枝
113 
114         // 找一個互不相等的排列（從小到大有序）
115         // 以初始排列為目前數字的編号
116         for(int i=1;i<=len;++i)
117         {
118             p[i]=i;
119         }
120         // 初始化最大最小值
121         minn=2e9;
122         maxx=-1;
123         // 自目前排列開始更新滿足條件時的最大最小值
124         do
125         {
126             update();
127         }while(next_permutation(p+1,p+len+1));  // 需要頭檔案algor
128         // 九位數的全排列，有362880種
129         // 最多嘗試次數，為九次
130         // 複雜度約為 10^7
131         printf("%d %d\n",minn,maxx);
132     }
133     return 0;
134 }