HDU 4726 Kia's Calculation （貪心）

思路：貪心，盡量先組大的數字，注意考慮前導零的情況

代碼：

#include 
#include 

const int N = 1000005;
int t, v1[10], v2[10], ans[N];
char s1[N], s2[N];

void solve() {
    int n = strlen(s1);
    if (n == 1) {
	ans[0] = (s1[0] - '0' + s2[0] - '0') % 10;
	printf(%d
, ans[0]);
	return;
    }
    for (int i = 9; i >= 0; i--) {
	int flag = 0;
	for (int j = 1; j <= 9; j++) {
	    int k = (10 + i - j) % 10;
	    if (k == 0) continue;
	    if (v1[j] && v2[k]) {
		v1[j]--;
		v2[k]--;
		ans[0] = i;
		flag = 1;
		break;
	    }
	}
	if (flag) break;
    }
    for (int i = 1; i < n; i++) {
	int flag = 0;
	for (int j = 9; j >= 0; j--) {
	    for (int k = 0; k <= 9; k++) {
		int kk = (10 + j - k) % 10;
		if (v1[k] && v2[kk]) {
		    v1[k]--;
		    v2[kk]--;
		    ans[i] = j;
		    flag = 1;
		    break;
		}
	    }
	    if (flag) break;
	}
    }
    int flag = 0;
    for (int i = 0; i < n; i++) {
	if (ans[i] != 0 || flag) {
	    printf(%d, ans[i]);
	    flag = 1;
	}
	if (flag == 0) continue;
    }
    if (flag == 0) printf(0);
    printf(
);
}

int main() {
    int cas = 0;
    scanf(%d, &t);
    while (t--) {
	memset(v1, 0, sizeof(v1));
	memset(v2, 0, sizeof(v2));
	scanf(%s%s, s1, s2);
	int l1 = strlen(s1), l2 = strlen(s2);
	for (int i = 0; i < l1; i++)
	    v1[s1[i] - '0']++;
	for (int i = 0; i < l2; i++)
	    v2[s2[i] - '0']++;
	printf(Case #%d: , ++cas);
	solve();
    }
    return 0;
}