首页 > 代码库 > Kia's Calculation(贪心)
Kia's Calculation(贪心)
http://acm.hdu.edu.cn/showproblem.php?pid=4726
大致题意:给两个长度小于10^6且相等的合法的正整数,你可以任意组合每个数中的数字,但不能有前导零。两个数相加的规则如题,相加不进位。问可以得到的A+B的最大值。
都看错题意了,一直以为数的大小是小于10^6,队友用了一个ms很高端的函数对字符串全排列,枚举求最大值。结果WA到死。其实是长度小于10^6,以后看题要细心再细心啊。。。
用数组记录每个数中每个数字的个数,每次都找从两个字符串中找和最大的,但求第一个数时要注意,不能有前导零。除了第一位,后面的每次找和最大的即可。最后别忘了去掉前导零,以及结果是0的特殊情况。
#include <stdio.h> #include <iostream> #include <map> #include <stack> #include <vector> #include <math.h> #include <string.h> #include <queue> #include <string> #include <stdlib.h> #include <algorithm> #define LL long long #define _LL __int64 #define eps 1e-8 #define PI acos(-1.0) using namespace std; const int maxn = 1000010; int fir[12],sec[12]; char s1[maxn],s2[maxn],ans[maxn]; int main() { int test,len; scanf("%d",&test); for(int item = 1; item <= test; item++) { scanf("%s %s",s1,s2); len = strlen(s1); memset(fir,0,sizeof(fir)); memset(sec,0,sizeof(sec)); if(strcmp(s1,"0") == 0) { printf("Case #%d: ",item); printf("%s\n",s2); continue; } if(strcmp(s2,"0") == 0) { printf("Case #%d: ",item); printf("%s\n",s1); continue; } for(int i = 0; i < len; i++) { fir[s1[i]-'0']++; sec[s2[i]-'0']++; } int cnt = 0; int Max = -1; int a,b; //找第一个数字,不能找前导零 for(int i = 1; i <= 9; i++) { if(fir[i] == 0) continue; for(int j = 1; j <= 9; j++) { if(sec[j] == 0) continue; int t = (i+j)%10; if(t > Max) { Max = t; a = i; b = j; } } } ans[++cnt] = Max + '0'; fir[a]--; sec[b]--; while(cnt < len) { Max = -1; for(int i = 0; i <= 9; i++) { if(fir[i] == 0) continue; for(int j = 0; j <= 9; j++) { if(sec[j] == 0) continue; int t = (i+j)%10; if(t > Max) { Max = t; a = i; b = j; } } } ans[++cnt] = Max + '0'; fir[a]--; sec[b]--; } printf("Case #%d: ",item); int i; for(i = 1; i <= len; i++) if(ans[i] != '0') break; //如果是0,直接输出0 if(i == len+1) printf("0\n"); else { for( ;i <= len; i++) printf("%c",ans[i]); printf("\n"); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。