「一本通 1.3 例 5」weight

形式化题目

给定一个包含 $2n$ 个正整数的多重集合，它是某长度为 $n$ 的未知正整数数列 $a_1, a_2, \dots, a_n$ 的所有前缀和 $\left\{\sum_{j=1}^i a_j \mid 1 \le i \le n\right\}$ 与所有后缀和 $\left\{\sum_{j=n-i+1}^n a_j \mid 1 \le i \le n\right\}$ 打乱顺序后的并集。同时给定一个合法数字集合 $S \subseteq \{1, 2, \dots, 500\}$ ，已知原数列的各项均满足 $a_i \in S$ 。

要求还原出数列 $a_1, a_2, \dots, a_n$ 。若存在多组满足条件的数列，输出字典序最小的一组。

正解

思路

因为数列中每一个数 $a_i \ge 1$ ，所以原数列的所有前缀和序列 $P_1 < P_2 < \dots < P_n$ 与所有后缀和序列 $S_1 < S_2 < \dots < S_n$ 都是严格单调递增的。

升序排序与双向归属：将输入的 $2n$ 个和升序排列为 $s_0 \le s_1 \le \dots \le s_{2n-1}$ 。显然，序列中最小的未分配和，必然对应着原序列中尚未确定的最靠左的前缀和，或者最靠右的后缀和。我们可以维护一个向中间收缩的填数区间 $[x, y]$ （初始为 $[1, n]$ ），以及当前已累计的前缀和 $pre$ （初始为 $0$ ）和后缀和 $suf$ （初始为 $0$ ）。
按位推导与剪枝：遍历排序后的每一个和 $s_k$ ：
- 若 $s_k$ 归属于前缀和，则左端新填入的数为 $d_1 = s_k - pre$ 。合法条件为 $0 < d_1 \le 500$ 且 $d_1 \in S$ 。若满足，则令 $pre \leftarrow s_k$ 并将区间左端右移（ $x \leftarrow x + 1$ ）。
- 若 $s_k$ 归属于后缀和，则右端新填入的数为 $d_2 = s_k - suf$ 。合法条件为 $0 < d_2 \le 500$ 且 $d_2 \in S$ 。若满足，则令 $suf \leftarrow s_k$ 并将区间右端左移（ $y \leftarrow y - 1$ ）。
由于每个数严格在集合 $S$ （最大 $500$ ）内，差值剪枝非常苛刻，绝大多数错误分支在第一步或第二步就会被立即剪掉。
终点检测与字典序最小：当左右指针重合（ $x = y$ ）时，序列只剩下最中间一个数未填。此时整个数列的总和已被最大和 $total = s_{2n-1}$ 唯一确定，中间这个数的值必然是 $rem = total - pre - suf$ 。只要检验 $0 < rem \le 500$ 且 $rem \in S$ ，即找到一组解。为了保证字典序最小，搜索中对于每一个和 $s_k$ ，优先尝试作为前缀和填充左侧，再尝试作为后缀和填充右侧。找到的第一组解即为字典序最小解。
Python 实现细节： $n \le 1000$ 时递归深度达 $1000$ ，采用显式栈模拟深度优先搜索，将状态和已确定的左右部分压栈，可彻底避免递归深度限制，运行速度极快。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-05 21:47
# update_at: 2026-07-05 21:47

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    sums = sorted([next(data) for _ in range(2 * n)])
    m = next(data)
    allowed = set([next(data) for _ in range(m)])
    total = sums[-1]

    # 显式栈模拟深度优先搜索，优先尝试作为前缀以保证字典序最小
    # 栈元素: (k, x, y, pre, suf, seq1, seq2)
    stack: list[tuple[int, int, int, int, int, tuple[int, ...], tuple[int, ...]]] = [
        (0, 1, n, 0, 0, (), ())
    ]

    while stack:
        k, x, y, pre, suf, s1, s2 = stack.pop()
        if x == y:
            rem = total - pre - suf
            if 0 < rem <= 500 and rem in allowed:
                print(*(list(s1) + [rem] + list(reversed(s2))))
                return
            continue

        # 后压入作为后缀的分支，先尝试作为前缀的分支
        diff_suf = sums[k] - suf
        if 0 < diff_suf <= 500 and diff_suf in allowed:
            stack.append((k + 1, x, y - 1, pre, sums[k], s1, s2 + (diff_suf,)))

        diff_pre = sums[k] - pre
        if 0 < diff_pre <= 500 and diff_pre in allowed:
            stack.append((k + 1, x + 1, y, sums[k], suf, s1 + (diff_pre,), s2))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 01:50
 * update_at: 2026-10-06 01:52
 */
#include <algorithm>
#include <iostream>
using namespace std;

const int MAXN = 1005;

typedef long long ll;

ll n;
ll sums[2 * MAXN]; // 打乱后排序的 2n 个前缀和、后缀和
ll ans[MAXN];      // ans[i] 为还原出的原数列第 i 项
ll total;          // 整个数列的总和，也就是最大的那个和
bool inS[505];     // inS[x] 表示 x 是否属于给定的合法数字集合 S

// 深度优先搜索：正处理第 k 个和，左右两端待填区间为 [x, y]，
// pre 是已确定的左端前缀和，suf 是已确定的右端后缀和。
// 优先把当前和当作前缀和填左侧，从而保证第一组解字典序最小。
bool dfs(ll k, ll x, ll y, ll pre, ll suf) {
    if (x == y) {
        ll rem = total - pre - suf; // 中间剩下的那一项
        if (rem >= 1 && rem <= 500 && inS[rem]) {
            ans[x] = rem;
            return true;
        }
        return false;
    }

    ll diff_pre = sums[k] - pre; // 当归为前缀和时，左侧新填的数
    if (diff_pre >= 1 && diff_pre <= 500 && inS[diff_pre]) {
        ans[x] = diff_pre;
        if (dfs(k + 1, x + 1, y, sums[k], suf)) {
            return true;
        }
    }

    ll diff_suf = sums[k] - suf; // 当归为后缀和时，右侧新填的数
    if (diff_suf >= 1 && diff_suf <= 500 && inS[diff_suf]) {
        ans[y] = diff_suf;
        if (dfs(k + 1, x, y - 1, pre, sums[k])) {
            return true;
        }
    }

    return false;
}

void solve() {
    cin >> n;
    ll len = 2 * n;
    for (ll i = 0; i < len; i++) {
        cin >> sums[i];
    }
    sort(sums, sums + len);

    ll m;
    cin >> m;
    for (ll i = 0; i < m; i++) {
        ll value;
        cin >> value;
        if (value >= 1 && value <= 500) {
            inS[value] = true;
        }
    }

    total = sums[len - 1]; // 最大的和就是整个数列的总和

    if (dfs(0, 1, n, 0, 0)) {
        for (ll i = 1; i <= n; i++) {
            if (i > 1) {
                cout << ' ';
            }
            cout << ans[i];
        }
        cout << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}

复杂度

时间复杂度：排序 $2n$ 个整数的时间为 $\mathcal{O}(n \log n)$ 。在剪枝搜索过程中，每步差值必须落在小集合 $S$ 内，搜索树宽度极窄（绝大多数节点只有单一可行后继），平均搜索步数仅为 $\mathcal{O}(n)$ ，总时间复杂度为 $\mathcal{O}(n \log n)$ 。
空间复杂度：存储排序后的前缀后缀和、集合 $S$ 以及搜索状态栈的空间复杂度均为 $\mathcal{O}(n)$ 。

总结

本题的关键在于利用前缀和与后缀和的双向单调递增性。将打乱的和排序后，问题转化为从两端向中间逼近的双指针决策过程。集合 $S$ 的取值范围极小，提供了强大的数值差剪枝条件，保证了深搜回溯的高效性。

图示解析

flowchart TD
    A["排序后的和序列 s[0] ≤ s[1] ≤ ... ≤ s[2n-1]"] --> B{"考虑当前未用的最小和 s[k]"}
    B -- "差值 s[k] - pre ∈ S (优先)" --> C["归为前缀和: a[x] = s[k] - pre, pre = s[k], x = x + 1"]
    B -- "差值 s[k] - suf ∈ S (后选)" --> D["归为后缀和: a[y] = s[k] - suf, suf = s[k], y = y - 1"]
    C --> E{"x == y ?"}
    D --> E
    E -- "否" --> B
    E -- "是" --> F["剩余中间项 rem = total - pre - suf<br/>若 rem ∈ S，输出字典序最小解"]

从左往右求和	从右往左求和
1=1	5=5
2=1+1	7=2+5
7=1+1+5	12=5+2+5
9=1+1+5+2	13=1+5+2+5
14=1+1+5+2+5	14=1+1+5+2+5