PAT甲题题解-1038. Recover the Smallest Number (30)-排序/贪心,自定义cmp函数的强大啊!!!
2024-10-20 02:18:33
博主欢迎转载,但请给出本文链接,我尊重你,你尊重我,谢谢~
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=; struct Node{
int len;
char str1[];
char str2[];
bool operator<(const Node tmp)const{ }
}node[maxn],rnode[maxn]; bool cmp(char*str1,char*str2){
if(strcmp(str1,str2)<=)
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=;i<n;i++){
scanf("%s",node[i].str1);
node[i].len=strlen(node[i].str1);
for(int j=;j<=/node[i].len;j++){
strcpy(node[i].str2+j*node[i].len,node[i].str1);
}
node[i].str2[]='\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=;i<n;i++){
if(!leadzero){
for(int j=;j<node[i].len;j++){
if(node[i].str1[j]!=''){
leadzero=true;
printf("%s",node[i].str1+j);
break;
}
}
}
else{
printf("%s",node[i].str1);
}
}
//如果全是0
if(!leadzero)
printf("0\n");
return ;
}
该题有个更好的解法那就是自定义排序的时候,我return a+b<b+a
想法太妙了,不得不说cmp函数的强大,哎自己受思维局限了。
想法出处:
http://www.liuchuo.net/archives/2303
最新文章
- .net 过滤特殊字符
- 使用maven创建Archetype
- 【HDU】1693 Eat the Trees
- Hadoop.2.x_时间服务器搭建(CentOs6.6)
- asp.net 微信企业号办公系统-表单及流程设计配置实例
- 事务并发处理: DB+ORM+逻辑代码
- Ajax解决缓存的5种方法
- Asp.net服务器控件在IE10下的不兼容问题
- Oracle游标循环更新数据案例
- BZOJ 1324 Exca 神剑 最小割
- centos6.8安装superctl 后台管理工具
- Centos 7部署大众点评CAT(二)——双服务器部署
- ie启动不了的解决办法,win7,win8都可以
- oracle、instantclient以及plsql安装包
- Windows提权与开启远程连接
- wap2app(十)--wap2app 添加原生底部导航,添加原生标题栏,填坑
- oracle12 安装
- word怎样从第三页开始设置页码
- Codeforces Round #131 Div1 B
- 1java异常详解