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): 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 10
6, 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;

	}

}