首页 > 代码库 > 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;
}
View Code

 

该题有个更好的解法那就是自定义排序的时候,我return a+b<b+a
想法太妙了,不得不说cmp函数的强大,哎自己受思维局限了。
想法出处:
http://www.liuchuo.net/archives/2303

PAT甲题题解-1038. Recover the Smallest Number (30)-排序/贪心,自定义cmp函数的强大啊!!!