HDU 4726 Kia's Calculation热身赛2 1011题(贪心 每次都找最大位的放在前面)

Kia's CalculationTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 268 Accepted Submission(s): 73


Problem DescriptionDoctor 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 ?
InputThe 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.
OutputFor test case X, output "Case #X: " first, then output the maximum possible sum without leading zeros.
Sample Input

159583036

Sample Output

Case #1: 8984

Source2013 ACM/ICPC Asia Regional Online —— Warmup2
题目大意：给你两个串，数位可以相互交换，问你两个串随意交换能组成最大和，注意这个加法是不进位的，而且0不能当头。
解题思路：贪心思想。每次都找两个和最大的放在最前面，第一位比较特殊都不可以取0，主要是先统计一下两个串0~9的个数。然后第一位确定了之后，如果第一位是0，就可以直接输出0了。每次在两个串里面找数位相加组成最大的，然后每次直接相当于批处理，至少让一个个数变成0。这样最多只会循环几十次，然后就break掉了。不过当时竟然跳不出循环。最后才发现是tmp取-1，因为到最后数位相加可能真的最大就是0.debug了半天。。。详见代码。
题目地址：Kia's Calculation
AC代码：

#include<iostream>#include<cstring>#include<string>#include<cmath>#include<cstdio>using namespace std;int a[10];int b[10];char t[1000005];char res[1000005];void debug()  //真心的，debug了很久{    int i;    for(i=0;i<10;i++)        cout<<a[i]<<" ";    cout<<endl;    for(i=0;i<10;i++)        cout<<b[i]<<" ";    cout<<endl;}int main(){    int tes,i,len,j,k;    scanf("%d",&tes);    int cas=0;    while(tes--)    {        for(i=0;i<10;i++)        {            a[i]=0,b[i]=0;        }        scanf("%s",t);        len=strlen(t);        for(i=0;i<len;i++)  //统计第一串的0~9的个数            a[t[i]-'0']++;        scanf("%s",t);        for(i=0;i<len;i++)  //统计第二串的0~9的个数            b[t[i]-'0']++;        int tmp=-1;   //这个地方真是个大坑，开始写的0        //debug();        int m,n;        for(i=1;i<10;i++)  //先找第一位，第一位不能是0，所以都是从1到9找的        {            if(a[i])            {                for(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\n",++cas);            continue;        }        a[m]--,b[n]--;  //两个串相应的数字个数减少一个        int p=1;        while(1)        {            int m,n;            tmp=-1;            int cnt=0;            for(i=0;i<10;i++)                if(!a[i])                  cnt++;            if(cnt==10)                break;            for(i=0;i<10;i++)            {                if(a[i])                {                    for(j=9;j>=0;j--)                    {                        if(b[j])                        {                            int tt=(i+j)%10;                            if(tt>tmp)                            {                                tmp=tt;                                m=i,n=j;                            }                        }                    }                }            }            int tm=a[m]<b[n]?a[m]:b[n];            a[m]-=tm,b[n]-=tm;  //每次找到之后直接让一个个数或者两个个数都变为0            for(k=p;k<p+tm;k++)                res[k]='0'+tmp;            p+=tm;        }        //debug();        res[p]='\0';        printf("Case #%d: %s\n",++cas,res);    }    return 0;}/*235958303612341241412412412421421412452342421231231321444678746758504556143364476573566354365553645675435364754364635433264630555555*/