思路:刚开始想复杂了。
看解题报告后才知道这题挺简单的,看来还是要多训练啊!!!
单独处理首位的数字,不能为0.其他的就好处理了,从大到小依次找下去就可以了……
代码如下:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include<iostream> 2 #include<stdio.h> 3 #include<algorithm> 4 #include<iomanip> 5 #include<cmath> 6 #include<cstring> 7 #include<vector> 8 #define ll __int64 9 #define pi acos(-1.0) 10 #define MAX 1000005 11 using namespace std; 12 char a[MAX],b[MAX]; 13 int c[11],d[11]; 14 int first() 15 { 16 int i,j; 17 for(i=9;i>=1;i--){ 18 for(j=1;j<=9;j++){ 19 if(i-j>0&&c[j]&&d[i-j]){ 20 c[j]--; 21 d[i-j]--; 22 break; 23 } 24 if(10+i-j<=9&&c[j]&&d[10+i-j]){ 25 c[j]--; 26 d[10+i-j]--; 27 break; 28 } 29 } 30 if(j<=9) break; 31 } 32 return i; 33 } 34 int solve(int x) 35 { 36 int t,ans=0; 37 for(int i=0;i<=9;i++){ 38 if(x-i>=0&&c[i]&&d[x-i]){ 39 t=min(c[i],d[x-i]); 40 c[i]-=t; 41 d[x-i]-=t; 42 ans+=t; 43 } 44 if(10+x-i<=9&&c[i]&&d[10+x-i]){ 45 t=min(c[i],d[10+x-i]); 46 c[i]-=t; 47 d[10+x-i]-=t; 48 ans+=t; 49 } 50 } 51 return ans; 52 } 53 int main(){ 54 int i,j,t,ca=0; 55 scanf("%d",&t); 56 while(t--){ 57 scanf("%s%s",&a,&b); 58 int len=strlen(a); 59 memset(c,0,sizeof(c)); 60 memset(d,0,sizeof(d)); 61 for(i=0;i<len;i++){ 62 c[a[i]-'0']++; 63 d[b[i]-'0']++; 64 } 65 int tt=first(); 66 printf("Case #%d: %d",++ca,tt); 67 if(tt==0){ 68 printf(" "); 69 continue; 70 } 71 for(i=9;i>=0;i--){ 72 int m=solve(i); 73 for(j=1;j<=m;j++) 74 printf("%d",i); 75 } 76 printf(" "); 77 } 78 return 0; 79 }