【P1012 拼数】题解

这是洛谷的P1012 拼数的题解.这篇文章先发布于洛谷题解,因此存在和此博客风格略有出入的情况,请忽略.

点击这里直达题目.

讲一个玄学的方法吧.我们可以充分利用STL函数来完成这个题目.然而因为对字符串的恐惧,我不打算用string…

首先我们可以想到进行一次排序.问题就在于排序的优先级.明显要比较两个数拼接是ab大还是ba大,而不是直接补齐位数直接排序(也就是字典序先后比较)(我一开始就是这么错的,反例:32132显然应该排成32321而不是32132).

我用了一种玄学的方法拼接数字.有一个东西叫做cmath,里面有一个东西叫pow(),还有一个log10().很显然,我们用(int)log10()就可以求出一个数有几位数(得到的结果是位数-1).我们就可以用(int)pow(10,(int)log10()+1)将一个数后面补上另一个数位数个0,之后再把它们加起来就实现了拼接数字.把这个东西写进比较函数(我用的是重载)(其实是之前错误解法的产物,懒得改了),就可以直接sort了!简单高效(常数贼大).

下面是代码.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAX=25;

struct num{
int val;

bool operator < (const num& b)const //重载小于号用于sort比较
{
return val*(int)pow(10,(int)log10(b.val)+1)+b.val>b.val*(int)pow(10,(int)log10(val)+1)+val; //用两种方式拼接比较大小
}
}a[MAX];

int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i].val);
sort(a+1,a+n+1); //sort大法好
for(int i=1;i<=n;i++) printf("%d",a[i].val);
return 0;
}

就是这样.

本文标题:【P1012 拼数】题解

文章作者:Snake

发布时间:2018年04月13日 - 21:04

最后更新:2018年04月28日 - 20:04

原始链接:https://snake.moe/2018/04/13/【P1012 拼数】题解/

许可协议: 署名-非商业性使用-相同方式共享 4.0 国际 转载请保留原文链接及作者。