HDU 4726 Kia's Calculation （贪心算法）

Time Limit: 2000/1000 MS ( Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 513 Accepted Submission(s): 142

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

2013 ACM/ICPC Asia Regional Online —— Warmup2

题意： 有2个合法的整数。 长度为 10^6。 数字的每一位都能移动， 但移动后的整数一定要是合法的， 即无前导零。 使得 A + B 最大

思路：贪心算法

import java.io.*;  
import java.util.*;  
  
public class Main {  
    BufferedReader bu;  
    PrintWriter pw;  
    int n;  
    int[] a = new int[12];  
    int[] b = new int[12];  
  
    public static void main(String[] args) throws IOException {  
        new Main().work();  
    }  
  
    void work() throws IOException {  
        bu = new BufferedReader(new InputStreamReader(System.in));  
        pw = new PrintWriter(new OutputStreamWriter(System.out), true);  
        n = Integer.parseInt(bu.readLine());  
        for (int p = 1; p <= n; p++) {  
  
            String s1 = bu.readLine();  
            String s2 = bu.readLine();  
  
            Arrays.fill(a, 0);  
            Arrays.fill(b, 0);  
              
            for (int i = 0; i < s1.length(); i++) {  
                a[s1.charAt(i) - '0']++;  
            }  
  
            for (int i = 0; i < s2.length(); i++) {  
                b[s2.charAt(i) - '0']++;  
            }  
            //获取第一个最大的数字  
            int t = getFirst();  
            pw.print("Case #"+p+": ");  
            pw.print(t);  
            if (t == 0) {//如果第一个数字为0，则后面的数字，都为0  
                pw.println();  
                continue;  
            }  
            // 获取后面的数字  
            for (int i = 9; i >





= 0; i--) {  
                int ans = 0;  
                for (int j = 0; j <= 9; j++) {  
                    if ((i - j >= 0) && a[j] != 0 && b[i - j] != 0) {  
                        int m = Math.min(a[j], b[i - j]);  
                        ans += m;  
                        a[j] -= m;  
                        b[i - j] -= m;  
                    }  
                    if ((10 + i - j <= 9) && a[j] != 0 && b[10 + i - j] != 0) {  
                        int m = Math.min(a[j], b[10 + i - j]);  
                        ans += m;  
                        a[j] -= m;  
                        b[10 + i - j] -= m;  
                    }  
                }  
                for (int j = 1; j <= ans; j++) {  
                    pw.print(i);  
                }  
            }  
            pw.println();  
        }  
    }  
    //获取第一个数字  
    int getFirst() {  
        int i, j;  
        for (i = 9; i >= 1; i--) {  
  
            for (j = 1; j <= 9; j++) {  
                if ((i - j > 0) && a[j] != 0 && b[i - j] != 0) {  
                    a[j]--;  
                    b[i - j]--;  
                    break;  
                }  
                if ((10 + i - j <= 9) && a[j] != 0 && b[10 + i - j] != 0) {  
                    a[j]--;  
                    b[10 + i - j]--;  
                    break;  
                }  
            }  
            if (j <= 9)  
                break;  
  
        }  
        return i;  
    }  
}