一本通 1.3 例 5」weight 显示标签 时间限制：C/C++ 1000MS，其他语言 2000MS 内存限制：C/C++ 256MB，其他语言 512MB 难度：普及 出题人： 描述 已知原数列 a 1 ​ ,a 2 ​ ,⋯,a n ​ 中的前 1 项，前 2 项，前 3 项， ⋯ ，前 n 项的和，以及后 1 项，后 2 项，后 3 项， ⋯ ，后 n 项的和，但是所有的数都被打乱了顺序。此外，我们还知道数列中的数存在于集合 S 中。试求原数列。当存在多组可能的数列时，求字典序最小的数列。 输入描述 第 1 行，一个整数 n 。 第 2 行， 2∗n 个整数，注意：数据已被打乱。 第 3 行，一个整数 m ，表示 S 集合的大小。 第 4 行， m 个整数，表示 S 集合中的元素。 输出描述 输出满足条件的最小数列。 用例输入 1 5 1 2 5 7 7 9 12 13 14 14 4 1 2 4 5 用例输出 1 1 1 5 2 5 提示 数据范围 对于 100% 的数据， 1 <= n <= 1000 ,1 <= m <= 500

以下是解决该问题的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)$。 [2026-02-02 17:23:38 | AI问答 | 716点数解答]