巧用 Python 破解“一本通 1.3 例 5”weight 数列难题！

以下是解决该问题的Python代码： ```python from itertools import permutations # 读取输入 n = int(input()) sums = list(map(int, input().split())) m = int(input()) S = set(map(int, input().split())) # 生成所有可能的数列 all_permutations = [] for p in permutations(S, n): all_permutations.append(list(p)) # 对所有可能的数列按字典序排序 all_permutations.sort() # 检查一个数列是否满足条件 def check_sequence(seq): prefix_sums = [] suffix_sums = [] # 计算前缀和 current_sum = 0 for num in seq: current_sum += num prefix_sums.append(current_sum) # 计算后缀和 current_sum = 0 for num in reversed(seq): current_sum += num suffix_sums.append(current_sum) # 合并前缀和与后缀和 combined_sums = prefix_sums + suffix_sums combined_sums.sort() sums.sort() # 检查是否与输入的和相等 return combined_sums == sums # 遍历所有可能的数列，找到满足条件的最小数列 for seq in all_permutations: if check_sequence(seq): print(" ".join(map(str, seq))) break ``` 代码解释： 1. 读取输入：首先读取整数`n`，表示数列的长度；接着读取`2*n`个整数，这些整数是打乱顺序的前缀和与后缀和；再读取整数`m`，表示集合`S`的大小；最后读取`m`个整数，组成集合`S`。 2. 生成所有可能的数列：使用`itertools.permutations`函数生成集合`S`中元素的所有长度为`n`的排列，将这些排列存储在`all_permutations`列表中。 3. 对所有可能的数列按字典序排序：使用`sort`方法对`all_permutations`列表进行排序，确保数列按字典序排列。 4. 检查一个数列是否满足条件：定义`check_sequence`函数，该函数接受一个数列作为参数，计算该数列的前缀和与后缀和，将它们合并并排序，然后与输入的和进行比较。如果相等，则返回`True`，否则返回`False`。 5. 遍历所有可能的数列，找到满足条件的最小数列：遍历`all_permutations`列表，对于每个数列，调用`check_sequence`函数进行检查。如果满足条件，则输出该数列并终止循环。 复杂度分析： - 时间复杂度：生成所有可能的数列的时间复杂度为$O(m^n)$，其中$m$是集合`S`的大小，$n$是数列的长度。对于每个数列，检查是否满足条件的时间复杂度为$O(n log n)$。总的时间复杂度为$O(m^n * n log n)$。 - 空间复杂度：主要的空间开销是存储所有可能的数列，空间复杂度为$O(m^n * n)$。 ######[AI问答 | 716点数解答 | 2026-02-02 17:23:38]