Farmer John's Favorite Permutation

题意

给定一个长度为 $N-1$ 的提示序列 h。它可能由某个 $1..N$ 的排列 p 经过如下过程得到：

比较当前排列的左右端点。
如果左端点更大，写下左端点右边的元素，并删除左端点。
否则，写下右端点左边的元素，并删除右端点。

要求恢复字典序最小的合法排列；如果不存在，输出 -1。

思路

先看一个小数据暴力：

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
93
94
95
96
97
98
99
100
101
102
103
104
105/**
 * 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 15:49
 * update_at: 2026-07-11 15:52
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10;

int T;
int n;
int h[MAXN];
int perm_arr[MAXN];
int best[MAXN];
bool used[MAXN];
bool found;

bool produce_same_h() {
    int tmp[MAXN];
    for (int i = 1; i <= n; i++) {
        tmp[i] = perm_arr[i];
    }

    int l = 1;
    int r = n;
    for (int i = 1; i <= n - 1; i++) {
        int wrote;
        if (tmp[l] > tmp[r]) {
            wrote = tmp[l + 1];
            l++;
        } else {
            wrote = tmp[r - 1];
            r--;
        }

        if (wrote != h[i]) return false;
    }

    return true;
}

void dfs_perm(int pos) {
    if (found) return;

    if (pos == n + 1) {
        if (produce_same_h()) {
            found = true;
            for (int i = 1; i <= n; i++) {
                best[i] = perm_arr[i];
            }
        }
        return;
    }

    // 小数据暴力：按字典序递归生成所有排列，找到第一个合法排列。
    for (int x = 1; x <= n; x++) {
        if (used[x]) continue;
        used[x] = true;
        perm_arr[pos] = x;
        dfs_perm(pos + 1);
        used[x] = false;
    }
}

void solve_one() {
    cin >> n;
    for (int i = 1; i <= n - 1; i++) {
        cin >> h[i];
    }

    found = false;
    for (int i = 1; i <= n; i++) {
        used[i] = false;
        best[i] = 0;
    }

    dfs_perm(1);

    if (!found) {
        cout << -1 << '\n';
        return;
    }

    for (int i = 1; i <= n; i++) {
        if (i > 1) cout << ' ';
        cout << best[i];
    }
    cout << '\n';
}

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

    cin >> T;
    while (T--) {
        solve_one();
    }

    return 0;
}

这个暴力按字典序枚举所有排列，模拟题目过程，找到第一个能产生 h 的排列。它只适合小数据。

关键观察一：最小值 1 永远不会被删除。

如果 1 在左端，它不可能大于右端；如果 1 在右端，左端一定大于它，会删除左端。因此最后两个剩余元素中一定有 1，最后写下的也一定是 1。

所以必须满足：

text

1h[N-1] == 1

关键观察二：去掉最后一个 1 后，前面的 $N-2$ 个提示值就是原排列中间 $N-2$ 个位置的元素。

因此它们不能重复。没有出现在这些提示值中的两个数，就是原排列的左右端点。

为了字典序最小，把较小的缺失数放左端，较大的放右端。

端点确定后，从左到右处理 h[1..N-2]：

如果当前左端点大于右端点，就把当前提示值填到左边内侧。
否则，把当前提示值填到右边内侧。

最后再模拟检查一次构造出的排列是否真的产生 h。

代码

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117/**
 * 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 15:49
 * update_at: 2026-07-11 15:52
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int T;
int n;
int h[MAXN];
int ans[MAXN];
bool used[MAXN];

bool check_answer() {
    int l = 1;
    int r = n;

    for (int i = 1; i <= n - 1; i++) {
        int wrote;
        if (ans[l] > ans[r]) {
            wrote = ans[l + 1];
            l++;
        } else {
            wrote = ans[r - 1];
            r--;
        }

        if (wrote != h[i]) return false;
    }

    return true;
}

void solve_one() {
    cin >> n;
    for (int i = 1; i <= n - 1; i++) {
        cin >> h[i];
    }

    if (h[n - 1] != 1) {
        cout << -1 << '\n';
        return;
    }

    for (int i = 1; i <= n; i++) {
        used[i] = false;
        ans[i] = 0;
    }

    bool ok = true;
    for (int i = 1; i <= n - 2; i++) {
        if (used[h[i]]) ok = false;
        used[h[i]] = true;
    }

    if (!ok) {
        cout << -1 << '\n';
        return;
    }

    int ends[3];
    int end_cnt = 0;
    for (int x = 1; x <= n; x++) {
        if (!used[x]) {
            end_cnt++;
            ends[end_cnt] = x;
        }
    }

    if (end_cnt != 2) {
        cout << -1 << '\n';
        return;
    }

    ans[1] = ends[1];
    ans[n] = ends[2];

    int l = 1;
    int r = n;
    for (int i = 1; i <= n - 2; i++) {
        if (ans[l] > ans[r]) {
            l++;
            ans[l] = h[i];
        } else {
            r--;
            ans[r] = h[i];
        }
    }

    if (!check_answer()) {
        cout << -1 << '\n';
        return;
    }

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

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

    cin >> T;
    while (T--) {
        solve_one();
    }

    return 0;
}

复杂度

每个测试用例线性扫描和构造。

时间复杂度为 $O(N)$ ，空间复杂度为 $O(N)$ 。

总结

本题的核心是从删除过程里找不变量：1 永远不会作为端点被删，所以最后提示必须是 1。

剩下的提示值确定中间元素，缺失值确定两端，然后按原规则反向构造即可。

Farmer John's Favorite Permutation

目录

题意

思路

代码

复杂度

总结