hdu 4726 Kia's Calculation 贪心

Kia's Calculation

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 4054    Accepted Submission(s): 825

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 10⁶, 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

2013 ACM/ICPC Asia Regional Online —— Warmup2

 

 

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#define ls (u<<1)
#define rs (u<<1|1)
#define maxn 1000005
#define ll long long
using namespace std;
#define max(a,b)    (a)>(b)?(a):(b)
#define min(a,b)    (a)<(b)?(a):(b)
int a[10],b[10];
char s1[maxn],s2[maxn],res[maxn];
int main(){
    int T;
    scanf("%d",&T);
    int t = 0;
    while(T--){
        for(int i=0;i<10;i++){
            a[i]=0,b[i]=0;
        }
        scanf("%s%s",s1,s2);
        int len = strlen(s1);
        for(int i=0;i<len;i++){
            a[s1[i]-'0'] ++;//统计第一串的0~9的个数  
            b[s2[i]-'0'] ++;//统计第二串的0~9的个数
        }
        int tmp = -1;//这个地方真是个大坑，开始写的0,记得这里要写一个负数，因为所有的数都大于0 
        int n,m;
        for(int i=1;i<10;i++){//先找第一位，第一位不能是0，所以都是从1到9找的
            if(a[i]){
                for(int j=1;j<10;j++){
                    if(b[j]){
                        if((i+j)%10>tmp){
                            tmp = (i+j)%10;
                            m=i,n=j;
                        }
                    }
                }
            }
        }
        res[0] = '0' + tmp; //第一位找到  
        if(res[0] == '0'){//如果第一位是0，说明后面也只能是0，直接输出0就可以了  
            printf("Case #%d: 0
",++t);
            continue;
        }
        a[m]--,b[n]--; //两个串相应的数字个数减少一个  
        int p = 1;
        while(1){
            int m,n,cnt=0;
            tmp = -1;
            for(int i=0;i<10;i++){
                if(!a[i]){
                    cnt++;
                }
            }
            if(cnt == 10){
                break;
            }
            for(int i=0;i<10;i++){
                if(a[i]){
                    for(int j=9;j>=0;j--){
                        if(b[j]){
                            int tmpt = (i+j)%10;
                            if(tmpt>tmp){
                                tmp = tmpt;
                                m=i,n=j;
                            }
                        }
                    }
                }
            }
            int tm = min(a[m],b[n]);
            //假设a，b组成一个值a，b这两个数都有多个，则直接减完，这样可以节省时间 
            a[m] -= tm,b[n] -= tm;//每次找到之后直接让一个个数或者两个个数都变为0 
            for(int k=p;k<p+tm;k++){
                res[k] = '0' + tmp;
            }
            p += tm;
        }        
        res[p] = '';
        printf("Case #%d: %s
",++t,res);
    } 
    return 0;
}