Kia's Calculation
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 624 Accepted Submission(s): 178
Problem Description
Doctor Ghee is teaching Kia how to calculate the sum of two integers. But Kia is so careless and alway forget to carry a number when the sum of two digits exceeds 9. For example, when she calculates 4567+5789, she will get 9246, and for 1234+9876, she will get 0. Ghee is angry about this, and makes a hard problem for her to solve: Now Kia has two integers A and B, she can shuffle the digits in each number as she like, but leading zeros are not allowed. That is to say, for A = 11024, she can rearrange the number as 10124, or 41102, or many other, but 02411 is not allowed. After she shuffles A and B, she will add them together, in her own way. And what will be the maximum possible sum of A "+" B ?
Input
The rst line has a number T (T <= 25) , indicating the number of test cases. For each test case there are two lines. First line has the number A, and the second line has the number B. Both A and B will have same number of digits, which is no larger than 106, and without leading zeros.
Output
For test case X, output "Case #X: " first, then output the maximum possible sum without leading zeros.
Sample Input
1 5958 3036
Sample Output
Case #1: 8984
Source
代码：786ms 采用数组存储，来做的...比较惊险的，卡过去了！！
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define maxn 1000000 //1e6
using namespace std;
char a[maxn+5],b[maxn+5],c[maxn+5];
void cal(int *str,char *a,int len)
{
for(int i=0;i<len;i++)
{
str[a[i]-'0']++;
}
}
int main()
{
int t,i,j,count=1,max,posi,posj,len1,k;
//freopen("test.in","r",stdin);
//freopen("test.out","w",stdout);
scanf("%d",&t);
while(t--)
{
int A[10]={0},B[10]={0},flag=0;
memset(a,'\0',sizeof a);
memset(b,'\0',sizeof b);
memset(c,'\0',sizeof c);
scanf("%s%s",a,b);
len1=strlen(a);
cal(A,a,len1);
cal(B,b,len1);
printf("Case #%d: ",count++);
for(k=1;k<=len1;k++)
{
max=-1;
for(i=9;i>=0;i--)
{
if(k==1&&i==0&&len1!=1) continue;
if(A[i])
{
for(j=9;j>=0;j--)
{
if(k==1&&j==0&&len1!=1) continue;
if(B[j])
{
int temp=(i+j)%10;
if(max<temp)
{
max=temp;
posi=i;
posj=j;
}
}
if(max==9)break;
}
}
if(max==9)break;
}
A[posi]--;
B[posj]--;
c[flag++]=max+'0';
}
if(flag>1)
{
if(c[0]>'0')
printf("%c",c[0]);
for(i=1;i<flag;i++)
{
printf("%c",c[i]);
if(c[0]<='0'&&c[i]=='0') break;
}
puts("");
}
else
printf("%c\n",c[0]);
}
return 0;
}