[NOIP1998 提高组] 拼数#洛谷

题目描述

设有 $n$ 个正整数 $a_1\dots a_n$，将它们联接成一排，相邻数字首尾相接，组成一个最大的整数。

输入格式

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

第二行有 $n$ 个整数，表示给出的 $n$ 个整数 $a_i$。

输出格式

一个正整数，表示最大的整数

样例 #1

样例输入 #1

3
13 312 343

样例输出 #1

34331213

样例 #2

样例输入 #2

4
7 13 4 246

样例输出 #2

7424613

提示

对于全部的测试点，保证 $1\le n\le 20$，$1\le a_i\le 10^9$。

NOIP1998 提高组 第二题

from functools import cmp_to_key


class Work:
    def __init__(self,v,n):
        self.value=v
        self.number=n


def cmp(x,y):
    if x.number<y.number:
        return 1
    elif x.number>y.number:
        return -1
    else:
        if x.value<y.value:
            return 1
        else:
            return -1

def get_value(x):
    srt=str(x)
    value_ans=int(srt[0])
    return value_ans


if __name__=="__main__":
    num = int(input())
    mapp = list(map(int, input().split()))
    value=[]
    for item in range(num):
        key=get_value(mapp[item])
        value.append(Work(mapp[item],key))
    value.sort(key=cmp_to_key(cmp))
    value_mapp=[]
    for item in value:
        value_mapp.append(str(item.value))
    value_ans=''.join(value_mapp)
    print(value_ans)

一开始想着通过判断第一位数字，如果第一位数字相同，就直接看谁大谁就在前面来排序，但是比如32和321就没法排序，我这里得到的是32132，但是正确的结果应该是32321.后来通过下面的代码来考虑：

from functools import cmp_to_key


def cmp(x,y):
    if x+y<y+x:
        return 1
    else:
        return -1


if __name__=="__main__":
    num = int(input())
    mapp = list(map(str, input().split()))
    mapp.sort(key=cmp_to_key(cmp))
    value_ans=''.join(mapp)
    print(value_ans)

这里的大于小于比较，是指的是字符串的字典序的比较，通过对每个选用的数进行字符串的拼接进行字典序的比较，对每次的拼接进行判断。而且这样的思想和代码都比较好理解。对于列表转换成字符串的操作之前有过总结。