python学习——洛谷 [NOIP1998 提高组] 拼数 两种方法
[NOIP1998 提高组] 拼数
题目描述
设有 n n n 个正整数 a 1 … a n a_1 \dots a_n a1…an,将它们联接成一排,相邻数字首尾相接,组成一个最大的整数。
输入格式
第一行有一个整数,表示数字个数 n n n。
第二行有 n n n 个整数,表示给出的 n n n 个整数 a i a_i ai。
输出格式
一个正整数,表示最大的整数
样例 #1
样例输入 #1
3
13 312 343
样例输出 #1
34331213
样例 #2
样例输入 #2
4
7 13 4 246
样例输出 #2
7424613
提示
对于全部的测试点,保证 1 ≤ n ≤ 20 1 \leq n \leq 20 1≤n≤20, 1 ≤ a i ≤ 1 0 9 1 \leq a_i \leq 10^9 1≤ai≤109。
NOIP1998 提高组 第二题
分析
思路来自于排序,常规的排序都是比较两个数的数值的大小,即a
与b
,而在这道题中,我们比较的是两个数拼接(a+b
与b+a
)的大小。
这道题核心在于python中并没有像C/C++能直接自定义sort
的comp
,而是要先导入functools
模块的cmp_to_key
的方法,然后再自定义函数。还有一个易错点就是自定义的comp
函数不能简单地返回a+b > b+a
,而是要根据大于等于小于分别返回-1,0,1
才能实现排序效果。
AC代码
from functools import cmp_to_key
def compare(a, b):
if a+b > b+a:
return -1
if a+b < b+a:
return 1
return 0
n = input()
nums = list(map(str, input().split()))
nums.sort(key=cmp_to_key(compare))
print(''.join(nums))
方法2
还有一个思路:
我们发现一般情况下当数值长度越少,高位的数越大,则越应该靠前,但这样不方便比较,因此我们先对数据进行处理,将位数少的数先用0进行补齐,再进行排序比较。
但这有一个缺陷,就是当数据都补0后如果数值相等,那怎么排序,如下图:
因此在排序中我们用两个指标,先按补0后的数值排,越大的越靠前,如果补0后数值相等,则按原始数值来排,越小的越靠前。
n = input()
num = [int(x) for x in input().split()]
max_len = len(str(max(num)))
for i in range(len(num)):
num[i] = [num[i], num[i] * 10 ** (max_len - len(str(num[i])))]
num.sort(key=lambda x:(x[1], -x[0]), reverse=True)
# print(num)
print(int(''.join(str(item[0]) for item in num)))
只能AC大部分数据,有待完善,望大佬指点