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 DescriptionInputOutputSample InputSample OutputSourceimport 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，则后面的数字，都为0pw.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;}}