The Best Lineup

题意

给定一排牛 a。FJ 从前往后依次移除 a 的第一头牛，每次可以选择是否把这头牛加入到新队伍 b 的末尾。

在这个过程开始前，FJ 最多可以把一头牛移动到它原来位置之前的任意位置。

要求输出在最优移动和最优选择加入策略下，可以得到的字典序最大的 b。

思路

先看一个小数据暴力。它枚举“不移动”和所有可能的前移操作，对每个新序列重新计算能得到的最优 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
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/**
 * 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 18:20
 * update_at: 2026-07-11 18:24
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 15;

int n;
int a[MAXN];

vector<int> get_best_lineup(vector<int> cur) {
    vector<int> res;
    int suffix_max = -1;

    for (int i = (int)cur.size() - 1; i >= 0; i--) {
        if (cur[i] >= suffix_max) {
            suffix_max = cur[i];
            res.push_back(cur[i]);
        }
    }

    reverse(res.begin(), res.end());
    return res;
}

bool lex_greater_vec(vector<int> x, vector<int> y) {
    int len = min((int)x.size(), (int)y.size());
    for (int i = 0; i < len; i++) {
        if (x[i] != y[i]) {
            return x[i] > y[i];
        }
    }
    return x.size() > y.size();
}

void solve_one_case() {
    cin >> n;
    vector<int> origin;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        origin.push_back(a[i]);
    }

    vector<int> best = get_best_lineup(origin);

    // 枚举把 old_pos 位置的牛移动到它之前的 insert_pos。
    for (int old_pos = 0; old_pos < n; old_pos++) {
        for (int insert_pos = 0; insert_pos <= old_pos; insert_pos++) {
            vector<int> cur = origin;
            int value = cur[old_pos];
            cur.erase(cur.begin() + old_pos);
            cur.insert(cur.begin() + insert_pos, value);

            vector<int> candidate = get_best_lineup(cur);
            if (lex_greater_vec(candidate, best)) {
                best = candidate;
            }
        }
    }

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

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

    int t;
    cin >> t;
    while (t--) {
        solve_one_case();
    }

    return 0;
}

暴力里有一个基础函数：对固定的 a，最优的 b 是从左到右出现的后缀最大值。

为什么？假设当前看到了 a[i]，如果后面还有更大的数，那么把 a[i] 放进 b 会让当前这一位变小，不如跳过它等待后面的更大值。如果 a[i] 已经等于后缀最大值，就可以把它放进 b，这样不会让字典序变差。

因此，不移动时的 b 就是所有满足：

a_i = \max(a_i, a_{i+1}, \ldots, a_N)

的位置。

接下来考虑一次前移。设原来的后缀最大值序列是：

text

1b[1], b[2], ..., b[m]

并记录它们在原数组中的位置 p[i]。如果把某个 b[i] 向前移动到 p[i-1] 后面，那么原来夹在 p[i-1] 和 p[i+1] 之间的一些元素，可能会在移动后变成新的后缀最大值，并被插入到答案中。

代码对每个 i 做这件事：

假设把 b[i] 前移到 b[i-1] 后面；
从 p[i+1]-1 往左扫描到 p[i-1]+1；
跳过原来的 p[i]；
找出这段里相对于右侧仍然是后缀最大值的元素；
如果能找到非空插入序列，就把它插入到 b[i] 后面，并立刻停止。

为什么找到第一个能插入的位置就停止？因为字典序首先比较最靠前的位置。越早插入新的合法元素，就越早让答案变长或变大，后面位置再怎么变化也不如这里重要。

实现时在 b 的开头和结尾各加一个哨兵：

text

1(N+1, -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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80/**
 * 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 18:20
 * update_at: 2026-07-11 18:24
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;

int n;
int a[MAXN];

void solve_one_case() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<pair<int, int> > b;

    // 不移动时，b 由原数组中的后缀最大值组成。
    int suffix_max = -1;
    for (int i = n - 1; i >= 0; i--) {
        if (a[i] >= suffix_max) {
            suffix_max = a[i];
            b.push_back(make_pair(a[i], i));
        }
    }
    reverse(b.begin(), b.end());

    // 哨兵方便统一处理第一个和最后一个后缀最大值。
    b.insert(b.begin(), make_pair(n + 1, -1));
    b.push_back(make_pair(-1, n));

    for (int i = 1; i + 1 < (int)b.size(); i++) {
        vector<pair<int, int> > add;
        suffix_max = b[i + 1].first;

        // 尝试把 b[i] 前移后，哪些中间元素会变成新的后缀最大值。
        for (int j = b[i + 1].second - 1; j > b[i - 1].second; j--) {
            if (j == b[i].second) {
                continue;
            }
            if (a[j] >= suffix_max) {
                suffix_max = a[j];
                add.push_back(make_pair(a[j], j));
            }
        }

        reverse(add.begin(), add.end());
        if (!add.empty()) {
            b.insert(b.begin() + i + 1, add.begin(), add.end());
            break;
        }
    }

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

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

    int t;
    cin >> t;
    while (t--) {
        solve_one_case();
    }

    return 0;
}

复杂度

每个测试用例线性构造原始后缀最大值序列，并在官方贪心过程里扫描候选区间。

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

总结

本题的关键是先把“选择加入 b”转化成后缀最大值序列。

一次前移的作用不是任意改变答案，而是让某段中原本不是后缀最大值的元素，变成可以插入的新后缀最大值。最早能产生插入的位置，就是字典序最优的位置。

目录

题意

思路

代码

复杂度

总结