LOJ10249「一本通 1.3 例 5」weight 题解

题目理解

我们有一个长度为 $n$ 的未知序列 $a_1, a_2, \cdots, a_n$，已知：

• 所有前缀和：$a_1, a_1+a_2, \cdots, a_1+\cdots+a_n$
• 所有后缀和：$a_n, a_{n-1}+a_n, \cdots, a_1+\cdots+a_n$
• 这些 $2n$ 个和值被打乱顺序给出
• 序列中的每个数都来自给定的集合 $S$

要求还原出字典序最小的原序列。

核心算法

算法标签：深度优先搜索 双指针构造 剪枝优化 字典序最小

关键思路

设前缀和为 $p_i = \sum_{k=1}^i a_k$，后缀和为 $s_i = \sum_{k=i}^n a_k$。

关键性质：

• $p_n = s_1$ 是总和，应该是 $2n$ 个数中的最大值
• $p_i + s_{i+1} = p_n$（对于 $1 \le i < n$）

算法流程

1. 数据预处理

sort(a + 1, a + 1 + 2 * n);  // 排序输入的2n个和值
S[x] = true;                 // 标记集合S中的有效数字

算法标签：排序 哈希标记

2. 深度优先搜索框架

搜索状态：(idx, L, R, sum_L, sum_R)

• idx：当前处理的输入数组下标
• L, R：当前要填充的结果数组左右边界
• sum_L：已确定的左部分和（前L-1项和）
• sum_R：已确定的右部分和（后R+1项和）

搜索策略：

// 尝试作为左边界扩展
if (S[ a[idx] - sum_L ] == true) {
    ans[L] = a[idx] - sum_L;
    dfs(idx + 1, L + 1, R, a[idx], sum_R);
}

// 尝试作为右边界扩展  
if (S[a[idx] - sum_R] == true) {
    ans[R] = a[idx] - sum_R;
    dfs(idx + 1, L, R - 1, sum_L, a[idx]);
}

3. 终止条件

当 L == R 时，只剩中间一个位置：

int mid = a[2 * n] - sum_L - sum_R;  // 总和减去左右部分和
if (S[mid] && mid >= 1 && mid <= maxm) {
    ans[L] = mid;
    // 输出解并标记找到
}

算法正确性分析

为什么这样搜索能保证字典序最小？

• 优先尝试左边界扩展（先填左边的位置）
• 在左边界扩展中，使用当前最小的可用数字（因为输入已排序）
• 一旦找到解立即返回，保证是第一个找到的字典序最小解

关键等式推导

对于左边界扩展：

• 当前前缀和 = a[idx]
• 已确定的前缀和 = sum_L
• 新加入的数 = a[idx] - sum_L

对于右边界扩展同理。

复杂度分析

• 最坏情况：$O(2^{2n})$，但实际剪枝效果很好
• 剪枝优化：
  • 数字必须在集合 $S$ 中
  • 数字范围限制 $[1, 500]$
  • 找到第一个解立即返回

算法标签总结

主要标签

• 深度优先搜索(DFS) - 核心算法框架
• 双指针构造 - 从两端向中间填充
• 剪枝优化 - 利用集合S和数值范围剪枝

技术标签

• 字典序最小 - 问题优化目标
• 状态设计 - 搜索状态参数设计
• 边界处理 - 中间位置的特殊处理

问题特征标签

• 序列重构 - 问题本质
• 约束满足 - 满足前缀后缀和条件
• 组合搜索 - 在解空间中寻找可行解

优化标签

• 可行性剪枝 - 提前排除不可能分支
• 贪心选择 - 优先选择字典序小的扩展

样例验证

对于样例：

n = 5
输入和值: 1 2 5 7 7 9 12 13 14 14  
S = {1, 2, 4, 5}

算法过程：

1. 排序输入：1 2 5 7 7 9 12 13 14 14
2. 识别总和为 14（最大值）
3. 通过DFS构造，得到解 1 1 5 2 5

这个解法通过巧妙的双端构造和深度优先搜索，高效地找到了字典序最小的合法序列。