【蓝桥】拼数

题目

题目描述

设有 n 个正整数 ,将它们联接成一排,相邻数字首尾相接,组成一个最大的整数。

输入描述

第一行有一个整数,表示数字个数 n。

第二行有 n 个整数,表示给出的 n 个整数 a i。

其中,1≤n≤20,1≤ai≤10^9。

输出描述

输出一个正整数,表示最大的整数

输入输出样例

示例1

输入

1
2
3
13 312 343

输出

1
34331213

示例2

输入

1
2
4
7 13 4 246

输出

1
7424613

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 128M

解题

源码

C++

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 <iostream>
#include <cstring>
#include<algorithm>
using namespace std;

string num[20];

bool cmp(string a, string b)
{
return a+b > b+a;
//这里是字符串拼接,搜的资料说字符串比较首先比较长度,其次比较大小。
//32 321如果用a>b则会称为32132,正确结果应该是32321
}
int main()
{
int N;
cin >> N;
for (int i = 0; i < N; i++)
cin >> num[i];
sort(num, num+N, cmp);
for (int i = 0; i < N; i++)
cout << num[i];
return 0;
}

Python

1
2
3
4
5
6
7
8
9
10
11
from itertools import *

n=int(input()) #输入个数
s=input().split() #输入序列

lst=list() #list类型lst,用来存全排列结果
for item in permutations(s):
a=''.join(item) # 将所有排列结果连到一起
lst.append(int(a)) # 将每个连到一起的排列结果存起来

print(max(lst)) # 输出最大的结果

总结

C++版

  1. string类型拼接后的结果不一定是大的在前面最好,所以在局部范围上需要判断A+B>B+A,切实尝试一下结果究竟对不对。

Python版

  1. python版本直接穷举所有可能,然后找出最大值就可以。屌!