第1题-超级重排

题目

Tk 有一个长度为 $n$ 的数组 $(a1, a_2, \ldots, a_n)$，Tk 定义这个数组的权值为 $\sum{i=1}^{n} a_i$。为了使数组的权值最大，Tk 提出如下超级重排流程：

1. 将所有元素的十进制表示按原序拼接成一个字符串；
2. 对该字符串中的所有字符进行重新排列；
3. 按照原元素的位数切分字符串，恢复为 $n$ 个新数字。

换句话说：收集所有数字的每一个单独的数位；对于每一个原始数字 $a_i$ 记录它的位数，你必须用收集到的所有数位构造 $n$ 个新数字，其中第 $j$ 个新数字的位数必须与原始数组中第 $j$ 个数字 $a_j$ 的位数相同。目标是找到一种分配方式，使这 $n$ 个新数字的总和最大。

输入描述

第一行输入一个整数 $n$，表示数组长度。
第二行输入 $n$ 个整数 $a_1, a_2, \ldots, a_n$，题目保证每个元素的十进制表示中不含字符 0。

输出描述

输出一个整数，表示经过超级重排后数组的最大权值。

（回忆版无样例，可直接用代码自测）

思路

位权贪心：设最大位数为 $v$，一个数在其第 $j$ 位（从最高位对齐编号）上的数位权值是 $10^{v-1-j}$，与它属于哪个数无关。把所有数位降序排序，按「位权从大到小」依次填入空位（位数长的数先占高位），总和最大。实现上逐「位级」j 从高到低，给每个还缺数位的数的当前位分配剩余最大的数位。

代码

import sys

def main():
    it = iter(sys.stdin.read().strip().split())
    n = int(next(it))

    sizes = []
    nums = []
    for _ in range(n):
        x = next(it)
        sizes.append(len(x))
        nums += list(x)
    sizes.sort(reverse=True)
    nums.sort()

    v = sizes[0]  # 最大的位数
    g = [["0"] * v for _ in range(n)]
    for j in range(v):
        for i in range(n):
            if j < v - sizes[i]:
                continue
            g[i][j] = nums.pop()

    g = [int("".join(i)) for i in g]
    print(sum(g))

if __name__ == "__main__":
    main()

来源：25秋招笔试真题-小红书0907（知乎专栏）（回忆版）