12559: 最大最小整数

greedy, strings, sortings, math http://cs101.openjudge.cn/practice/12559

假设有n个正整数，将它们连成一片，将会组成一个新的大整数。现需要求出，能组成的最大最小整数。

比如，有4个正整数，23，9，182，79，连成的最大整数是97923182，最小的整数是18223799。

输入

第一行包含一个整数n，1<=n<=1000。第二行包含n个正整数，相邻正整数间以空格隔开。

输出

输出为一行，为这n个正整数能组成的最大的多位整数和最小的多位整数，中间用空格隔开。

样例输入

Sample1 in:
4
23 9 182 79

Sample1 out:
97923182 18223799

样例输出

Sample2 in:
2
11 113

Sample2 out:
11311 11113

提示

位数不同但前几位相同的时候。例如： 898 8987，大整数是898+8987，而不是8987+898。

来源：cs10116 final exam

思路：先拼接出最小值：即字典序最小；要保证每一个小的字符串，左移到合适位置，需要两两比较（刚好是冒泡排序）。这个题目是个不容易的，字符串处理题目。

求minimum时，对相邻两strA[k]与A[k+1]，比较A[k]+A[k+1]与A[k+1]+A[k]的大小，若A[k+1]+A[k]大，颠倒A[k]与A[k+1]；最多交换len(A)-1次。求maximum时，颠倒求minimum时的有序序列即可。使用冒泡排序，循环(n-1)次。

把这些数当成字符串处理，然后采用类似冒泡排序的做法排出大小。

python

# O(n^2)
n = int(input())
nums = input().split()
for i in range(n - 1):
    for j in range(i+1, n):
        #print(i,j)
        if nums[i] + nums[j] < nums[j] + nums[i]:
            nums[i], nums[j] = nums[j], nums[i]

ans = "".join(nums)
nums.reverse()
print(ans + " " + "".join(nums))

python

# 两倍长度是正确的。O(nlogn)
from math import ceil
input()
lt = input().split()

max_len = len(max(lt, key = lambda x:len(x)))
lt.sort(key = lambda x: x * ceil(2*max_len/len(x)))
lt1 = lt[::-1]
print(''.join(lt1),''.join(lt))

2020fall-cs101，黄旭
思路：这道题的关键应该是找到排序的方式，前一个数和后一个数比较，如果位数不足，就要重新从第一位开始比，所以说我就先取这个数列的最大位数，然后把每个数都扩充到相同位数进行比较，就可以了。
python
# 虽然能AC，但实际上不对。两倍长度是正确的。
from math import ceil
input()
lt = input().split()

max_len = len(max(lt, key = lambda x:len(x)))
lt.sort(key = lambda x: tuple([int(i) for i in x]) * ceil(max_len/len(x)))
lt1 = lt[::-1]
print(''.join(lt1),''.join(lt))

2020fall-cs101，蓝克轩。

在比较的部分卡了一下，因为python 2的sort有个cmp而python3没有，上网查了下，需要用functools里的cmp_to_key化成key的函数就可以了。

python

import functools
def compare(x, y):
	return(int(x+y) - int(y+x))
def compare_(x, y):
	return(int(y+x) - int(x+y))

n = int(input())
L = list(map(str, input().split()))
L = sorted(L, key=functools.cmp_to_key(compare_))
print(''.join(x for x in L), end=' ')
L = sorted(L, key=functools.cmp_to_key(compare))
print(''.join(x for x in L))

python

# 2024 焦玮宸 数学科学学院
from functools import cmp_to_key
def cmp(a, b):
    if int(a + b) > int(b + a):
        return 1
    elif int(a + b) < int(b + a):
        return -1
    else:
        return 0

_ = int(input())
nums = sorted(list(input().split()),key=cmp_to_key(cmp))
print("".join(nums[::-1]), "".join(nums))

时间复杂度分析

读取输入：
- 读取 n 和 s 的时间复杂度是 (O(n))，其中 (n) 是输入的数字个数。
排序：
- sort 方法的时间复杂度通常是 (O(n log n))，其中 (n) 是列表的长度。
- 自定义比较函数 cmp_max 的时间复杂度是 (O(1))（假设字符串拼接操作的时间复杂度为常数，因为字符串长度是固定的）。
- 因此，整个排序操作的时间复杂度是 (O(n log n))。
生成最大值和最小值：
- join 操作的时间复杂度是 (O(n))，因为需要遍历整个列表。
- reverse 操作的时间复杂度也是 (O(n))。

综合时间复杂度

读取输入：(O(n))
排序：(O(n log n))
生成最大值和最小值：(O(n))

因此，整个程序的时间复杂度是 (O(n log n))。

构造一个映射f，对每一个数A，若其位数是a，定义 $f (A) = A / 10^{a} - 1$ ；下证：将所有这些数字按照f(a)从大到小排序之后，组成的就是最大数！这是因为：首先，对于两个相邻的数A和B，若他们的位数分别是a和b，则AB大于BA等价于 $10^{b} * A + B > 10^{a} * B + A$ ；这又等价于 $(10^{b} - 1) A > (10^{a} - 1) B$ ，亦即f(A)大于f(B)！因此，在达到最大数时，f(a)一定是单调递减的（否则可交换使其变得更大，矛盾）；同样的，在达到最小数时，f(a)一定是单调递增的；证毕！

python

# 李彦臻 2300010821 数学科学学院
_ = input()
nums = input().split()

# 使用列表推导式直接创建包含原数字和其对应f(A)值的元组列表
function_values = [(A, int(A) / (10 ** len(A) - 1)) for A in nums]

# 按照f(A)值排序，使用sorted函数并指定key参数
sorted_by_value = sorted(function_values, key=lambda x: x[1])

# 提取排序后的数字部分
sorted_nums = [num for num, _ in sorted_by_value]

# 生成最小值和最大值的字符串
minv = ''.join(sorted_nums)
maxv = ''.join(sorted_nums[::-1])  # 直接反转列表得到最大值

print(f"{maxv} {minv}")

如何比较两个数在拼接后的大小关系，并据此对多个数进行排序。我们可以通过逐步分析来理解这句话。
一、问题背景 假设我们有两个数 A 和 B ，它们的位数分别为 a 和 b 。我们需要比较两种拼接方式 AB 和 BA 的大小。
拼接方式
**拼接方式 AB **：
A 有 a 位， B 有 b 位。 AB 表示将 B 拼接到 A 的末尾。
数学上，表示为：$ AB = A \times 10^b + B $。
**拼接方式 BA **：表示为：$ BA = B \times 10^a + A $。
何时 AB 更大 为了判断 ( AB ) 是否大于 ( BA )，我们进行如下推导： $A B > B A ⟹ A \times 10^{b} + B > B \times 10^{a} + A$
移项整理： $A \times 10^{b} - A > B \times 10^{a} - B$
提取公因式： $A (10^{b} - 1) > B (10^{a} - 1)$
两边同时除以 $ (10^a - 1) $ 和 $ (10^b - 1) $：$ \frac{A}{10^a - 1} > \frac{B}{10^b - 1} $
结论从上述推导可以看出，当 $\frac{A}{10^{a} - 1}$ 较大时， AB 会大于 BA 。也就是说，如果 $\frac{A}{10^{a} - 1}$ 较大，那么将 A 排在前面时，整个拼接后的数会更大。
二、排序策略 基于这一结论，我们可以对多个数进行排序，使得拼接后的结果最大。具体步骤如下：
计算每个数的比值：对于每个数 ( A )，计算 $\frac{A}{10^{a} - 1}$ ，其中 a 是 A 的位数。
排序：根据计算的比值对数进行降序排序。
拼接：按照排序后的顺序拼接这些数。
示例假设我们有三个数：123, 45, 678。
计算比值：
123 的位数 a = 3 ，比值 $\frac{123}{10^{3} - 1} = \frac{123}{999} \approx 0.1231$
45 的位数 b = 2 ，比值 $\frac{45}{10^{2} - 1} = \frac{45}{99} \approx 0.4545$
678 的位数 c = 3 ，比值 $\frac{678}{10^{3} - 1} = \frac{678}{999} \approx 0.6786$
排序：
比值从大到小排序：678, 45, 123
拼接：
按照排序后的顺序拼接：67845123
因此，拼接后的最大数是 67845123。

12559: 最大最小整数 ​

12559: 最大最小整数