最大整数

题目描述

设有n个正整数 (n<=20), 将它们连接成一排, 组成一个最大的多位整数.

例如: n=3时, 3个整数13, 312, 343连接成的最大整数为: 34331213

又如: n=4时, 4个整数7,13,4,246连接成的最大整数为: 7424613

输入输出格式

输入格式：

n n个数

输出格式：

连接成的多位数

输入输出样例

输入样例

3
13 312 343

输出样例

34331213

这道题是一道贪心题，将最高位大的数放在前面。两个数比较时，只用比较高位：若 num[i] 的高位大于 num[j] 的高位，则返回 num[i] > num[j]；否则下一位比较。

但大多数情况下两个数位数并不相同，而且如果这两个数位数相同的部分数字也恰好相等，就需要另作考虑：刚开始我想直接返回位数大的数值就大，但这其实是不全面的的，比如说 223 和 22，就返回 223 > 22，排的时候就是 22322，是对的；但是若 221 和 22，仍返回 221 > 22，合成为 222122，但应该是 22221。

我就又想了想：出现上一种情况后，应该再比较位数小的数的最后一位 num[l1 - 1] 和位数大的数的 num[l1]。还是char a[] = {"221"} 和 b[] = {"22"}，应该再比较一下 a[2] 和 b[1] ，因为 a[2] < b[1]，所以返回 a < b，a 排在 b 后面。

对于以上这种排序规则，用代码实现的话可以定义用结构体排序，重载 < 运算符。

就这样

 1 struct NUM
 2 {
 3     char num[15];
 4     bool operator < (const NUM& other)const
 5     {
 6         int l1 = strlen(num), l2 = strlen(other.num);
 7         int i = 0;
 8         while(i < min(l1, l2))
 9         {
10             if(num[i] == other.num[i]) i++;
11             else return num[i] > other.num[i]; 
12         }
13         if(l1 > l2) return num[l2] > other.num[l2 - 1];
14         else return num[l1 - 1] > other.num[l1];
15     }
16 }a[25];

完整代码

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 struct NUM
 8 {
 9     char num[15];
10     bool operator < (const NUM& other)const
11     {
12         int l1 = strlen(num), l2 = strlen(other.num);
13         int i = 0;
14         while(i < min(l1, l2))
15         {
16             if(num[i] == other.num[i]) i++;
17             else return num[i] > other.num[i]; 
18         }
19         if(l1 > l2) return num[l2] > other.num[l2 - 1];
20         else return num[l1 - 1] > other.num[l1];
21     }
22 }a[25];
23 int n;
24 char ans[1005];
25 int main()
26 {
27     scanf("%d", &n);
28     for(int i = 1; i <= n; ++i) scanf("%s", a[i].num);
29     sort(a + 1, a + n + 1);
30     for(int i = 1; i <= n; ++i)
31         strcat(ans, a[i].num);　　//用 cstring 库里的 strcat 函数，将 a[i].num 复制到 ans 的后面，返回 ans
32     printf("%s
", ans);
33     return 0;
34 }

当然也可以不用结构体排序，自己写一个 cmp 比较函数，效果都一样。