首页 > 代码库 > PAT甲题题解-1038. Recover the Smallest Number (30)-排序/贪心,自定义cmp函数的强大啊!!!
PAT甲题题解-1038. Recover the Smallest Number (30)-排序/贪心,自定义cmp函数的强大啊!!!
博主欢迎转载,但请给出本文链接,我尊重你,你尊重我,谢谢~
http://www.cnblogs.com/chenxiwenruo/p/6789138.html
特别不喜欢那些随便转载别人的原创文章又不给出链接的
所以不准偷偷复制博主的博客噢~~
题意:给出n个数,求拼接后值最小的数是多少。
一开始就简单的把所有字符串先从小到大拍个序,然后拼接起来去掉前导零,
结果发现有个问题,比如下面两个
32 32321
如果按常规字符串比较,32是在32321前面。
然而,32321-32才是较小的方案
如何有个好的比较方法?
使得32>32321
采用了重复填充的方法,直到填满8位为止,因为题目中每个数字最多8位
即将32->32(323232)
321->321(32132)
这样的话,前面就大于后面的了。输出的时候还是输出原来的即可
#include <iostream> #include <cstdio> #include <algorithm> #include <string.h> #include <cmath> #include <map> #include <vector> using namespace std; const int maxn=10005; struct Node{ int len; char str1[10]; char str2[20]; bool operator<(const Node tmp)const{ } }node[maxn],rnode[maxn]; bool cmp(char*str1,char*str2){ if(strcmp(str1,str2)<=0) return true; else return false; } bool cmpNode(Node a,Node b){ return cmp(a.str2,b.str2); } int main() { int n; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%s",node[i].str1); node[i].len=strlen(node[i].str1); for(int j=0;j<=8/node[i].len;j++){ strcpy(node[i].str2+j*node[i].len,node[i].str1); } node[i].str2[8]=‘\0‘; } sort(node,node+n,cmpNode); //for(int i=0;i<n;i++){ // printf("%s ",node[i].str2); //} //printf("\n"); bool leadzero=false; //反过来即是所求的最小数字 for(int i=0;i<n;i++){ if(!leadzero){ for(int j=0;j<node[i].len;j++){ if(node[i].str1[j]!=‘0‘){ leadzero=true; printf("%s",node[i].str1+j); break; } } } else{ printf("%s",node[i].str1); } } //如果全是0 if(!leadzero) printf("0\n"); return 0; }
该题有个更好的解法那就是自定义排序的时候,我return a+b<b+a
想法太妙了,不得不说cmp函数的强大,哎自己受思维局限了。
想法出处:
http://www.liuchuo.net/archives/2303
PAT甲题题解-1038. Recover the Smallest Number (30)-排序/贪心,自定义cmp函数的强大啊!!!
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。