(贪心法)组合最大数。 设有n个正整数，将它们连接成一排，组成一个最大的多位整数。 【Input】 第一行输入正整数n（n<5） 第二行输入n个正整数。 【Output】 最大的多位整数。 【Sample Input】 3 13 343 312 【Sample Output】 34331213 算法思路

这是一个经典的贪心算法问题，可以使用字符串进行处理。具体思路如下：

1. 定义一个字符串列表 `num_list`，用于存储输入的 n 个正整数。
2. 定义一个新的比较函数 `compare`，用于对两个字符串进行比较。对于两个字符串 S1 和 S2，如果 S1 + S2 比 S2 + S1 大，则 S1 应该排在 S2 前面；否则 S2 应该排在 S1 前面。这个比较函数的实现可以使用字符串的比较操作。
3. 对 `num_list` 进行排序，排序的依据是 `compare` 函数。排序后，将 `num_list` 中的所有字符串按顺序连接起来，就是组成的最大的多位整数。

以下是具体的 Python 代码实现：

n = int(input())
num_list = input().split()

# 定义比较函数
def compare(s1, s2):
    if s1 + s2 > s2 + s1:
        return -1
    else:
        return 1

# 对 num_list 进行排序
num_list = sorted(num_list, key=functools.cmp_to_key(compare))

# 将排序后的字符串连接起来
result = ''.join(num_list)

print(result)

这个算法的时间复杂度是 O(nlogn)，其中 n 是输入的正整数的个数。

相关问题

设有 nn 个正整数 a_1 \dots a_na 1 ​ …a n ​ ，将它们联接成一排，相邻数字首尾相接，组成一个最大的整数。

将这些正整数按照一定的规则排序，然后将它们依次连接起来，就可以组成一个最大的整数。具体来说，对于两个正整数 a 和 b，如果将它们连接起来得到的数 ab 大于 ba，那么就将 a 排在 b 的前面，否则将 b 排在 a 的前面。按照这个规则对所有的正整数进行排序，然后将它们依次连接起来，就可以得到一个最大的整数。

怎么用C语言实现：设有n个正整数，将它们连接成一排，组成一个最大的多位整数。 例如：n=3时，3个整数13，312，343，连成的最大整数为34331213。 又如：n=4时，4个整数7，13，4，246，连成的最大整数为7424613。

这道问题可以考虑使用字符串的排序来实现。将输入的n个正整数全部转换成字符串，然后将这些字符串按照字典序进行排序，最后将排序后的字符串进行拼接即可得到组成的最大整数。

C语言的代码实现如下：

#include <stdio.h>
#include <string.h>
#define MAXN 100

char num[MAXN][MAXN];  // 存储输入的数

int cmp(char* a, char* b) {
    char tmp1[MAXN * 2], tmp2[MAXN * 2];
    strcpy(tmp1, a);
    strcat(tmp1, b);
    strcpy(tmp2, b);
    strcat(tmp2, a);
    return strcmp(tmp2, tmp1);
}

int main() {
    int n, i, j;
    printf("请输入n的值：");
    scanf("%d", &n);
    printf("请输入%d个正整数：\n", n);
    for (i = 0; i < n; i++) {
        scanf("%s", num[i]);
    }
    // 用冒泡排序按照 cmp 规则排序
    for (i = 0; i < n - 1; i++) {
        for (j = i + 1; j < n; j++) {
            if (cmp(num[i], num[j]) < 0) {
                char tmp[MAXN];
                strcpy(tmp, num[i]);
                strcpy(num[i], num[j]);
                strcpy(num[j], tmp);
            }
        }
    }
    printf("组成的最大整数为：\n");
    for (i = 0; i < n; i++) {
        printf("%s", num[i]);
    }
    return 0;
}

注意：这个算法的时间复杂度为O(n^2)，如果n很大，可能会超时。实际上，这个问题还有更好的时间复杂度为O(nlogn)的实现方法，即使用快排或归并排序，具体实现可以自行探究。