首页 > 代码库 > HDU 4726 Kia's Calculation (贪心)
HDU 4726 Kia's Calculation (贪心)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4726
思路:贪心,尽量先组大的数字,注意考虑前导零的情况
代码:
#include <stdio.h> #include <string.h> 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\n", 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("\n"); } 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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。