Photoshoot

题意

有一个 1..N 的排列 a[1..N]。

现在给出 N-1 个数：

text

1b[i] = a[i] + a[i+1]

要求恢复一个满足条件的排列 a。如果有多个，输出字典序最小的。

思路

暴力想法

小数据可以直接按字典序枚举所有排列，检查相邻和是否等于 b[]：

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/**
 * 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-11 14:29
 * update_at: 2026-07-11 14:30
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 15;

int n;
int b[MAXN]; // b[i] = a[i] + a[i+1]
int p[MAXN];

bool check_perm() {
    for (int i = 1; i < n; i++) {
        if (p[i] + p[i + 1] != b[i]) {
            return false;
        }
    }
    return true;
}

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

    cin >> n;
    for (int i = 1; i < n; i++) {
        cin >> b[i];
    }

    // 小数据暴力：按字典序枚举所有排列，第一个合法排列就是答案。
    for (int i = 1; i <= n; i++) {
        p[i] = i;
    }

    do {
        if (check_perm()) {
            for (int i = 1; i <= n; i++) {
                if (i > 1) {
                    cout << ' ';
                }
                cout << p[i];
            }
            cout << '\n';
            return 0;
        }
    } while (next_permutation(p + 1, p + n + 1));

    return 0;
}

这种做法能直接表达题意，但全排列有 N! 种，只适合小数据。

枚举首项

观察相邻和关系：

text

1b[i] = a[i] + a[i+1]

如果已经知道 a[i]，那么下一项就被唯一确定：

text

1a[i+1] = b[i] - a[i]

所以只要枚举 a[1]，就能递推出整个排列。

字典序首先比较第一项，因此从 1 到 N 枚举 a[1]，第一个合法排列就是字典序最小的答案。

合法性检查包括两点：

每个数都在 1..N 范围内；
每个数只出现一次。

代码

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/**
 * 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-11 14:29
 * update_at: 2026-07-11 14:30
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int n;
int b[MAXN];   // b[i] = a[i] + a[i+1]
int ans[MAXN]; // 当前尝试得到的排列
bool used[MAXN];

bool build_and_check(int first_value) {
    memset(used, 0, sizeof(used));

    ans[1] = first_value;
    for (int i = 2; i <= n; i++) {
        ans[i] = b[i - 1] - ans[i - 1];
    }

    for (int i = 1; i <= n; i++) {
        if (ans[i] < 1 || ans[i] > n) {
            return false;
        }
        if (used[ans[i]]) {
            return false;
        }
        used[ans[i]] = true;
    }

    return true;
}

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

    cin >> n;
    for (int i = 1; i < n; i++) {
        cin >> b[i];
    }

    // 从小到大枚举 a[1]，第一个合法排列就是字典序最小。
    for (int first_value = 1; first_value <= n; first_value++) {
        if (build_and_check(first_value)) {
            for (int i = 1; i <= n; i++) {
                if (i > 1) {
                    cout << ' ';
                }
                cout << ans[i];
            }
            cout << '\n';
            return 0;
        }
    }

    return 0;
}

复杂度

枚举 a[1] 有 N 种可能，每次递推和检查是 $O(N)$ ，所以时间复杂度为 $O(N^2)$ 。

使用数组保存输入、答案和出现标记，空间复杂度为 $O(N)$ 。

总结

这题的突破口是：首项一旦确定，整段排列就被相邻和唯一决定。

因此不用枚举全排列，只要从小到大枚举首项并检查构造出的序列是否合法。

目录

题意

思路

暴力想法

枚举首项

代码

复杂度

总结