Livestock Lineup

题意

有 8 头固定名字的奶牛，需要安排一个挤奶顺序。

每条限制形如 X must be milked beside Y，表示 X 和 Y 必须相邻。

要求输出满足所有限制的字典序最小顺序。

思路

选择序列暴力

可以把 8 个位置看成一串选择：第 dep 个位置选择一头还没用过的奶牛。

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-07-11 14:45
 * update_at: 2026-07-11 14:46
 */
// brute.cpp：小数据暴力解，使用选择序列递归枚举所有挤奶顺序。
#include <bits/stdc++.h>
using namespace std;

const int COW_CNT = 8;
const int MAXN = 10;

int n;
string cows[COW_CNT] = {
    "Beatrice",
    "Belinda",
    "Bella",
    "Bessie",
    "Betsy",
    "Blue",
    "Buttercup",
    "Sue"
};

string need_a[MAXN], need_b[MAXN]; // need_a[i] 必须和 need_b[i] 相邻
string choose_cow[COW_CNT];        // choose_cow[dep] 表示第 dep 个位置选择的奶牛
bool used[COW_CNT];
bool found;

int find_pos_in_choose(string name) {
    for (int i = 0; i < COW_CNT; i++) {
        if (choose_cow[i] == name) {
            return i;
        }
    }
    return -1;
}

bool check_order() {
    for (int i = 1; i <= n; i++) {
        int pos_a = find_pos_in_choose(need_a[i]);
        int pos_b = find_pos_in_choose(need_b[i]);
        if (abs(pos_a - pos_b) != 1) {
            return false;
        }
    }
    return true;
}

void dfs_build(int dep) {
    if (found) {
        return;
    }

    if (dep == COW_CNT) {
        if (check_order()) {
            for (int i = 0; i < COW_CNT; i++) {
                cout << choose_cow[i] << '\n';
            }
            found = true;
        }
        return;
    }

    // 第 dep 个位置选择一头还没使用过的奶牛。按字典序枚举，保证第一个合法解最小。
    for (int i = 0; i < COW_CNT; i++) {
        if (used[i]) {
            continue;
        }
        used[i] = true;
        choose_cow[dep] = cows[i];
        dfs_build(dep + 1);
        used[i] = false;
    }
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        string t;
        cin >> need_a[i] >> t >> t >> t >> t >> need_b[i];
    }

    dfs_build(0);

    return 0;
}

这个暴力按字典序递归生成完整排列，在叶子节点统一检查所有相邻限制。

全排列枚举

因为只有 8 头奶牛：

text

18! = 40320

直接枚举全排列即可。

把 8 个名字先按字典序排好，然后使用 next_permutation 枚举。每次检查所有限制：

text

1abs(pos[X] - pos[Y]) == 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/**
 * 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:45
 * update_at: 2026-07-11 14:46
 */
#include <bits/stdc++.h>
using namespace std;

const int COW_CNT = 8;
const int MAXN = 10;

int n;
string order_cow[COW_CNT] = {
    "Beatrice",
    "Belinda",
    "Bella",
    "Bessie",
    "Betsy",
    "Blue",
    "Buttercup",
    "Sue"
};

string need_a[MAXN], need_b[MAXN]; // need_a[i] 必须和 need_b[i] 相邻

int find_pos(string name) {
    for (int i = 0; i < COW_CNT; i++) {
        if (order_cow[i] == name) {
            return i;
        }
    }
    return -1;
}

bool check_order() {
    for (int i = 1; i <= n; i++) {
        int pos_a = find_pos(need_a[i]);
        int pos_b = find_pos(need_b[i]);
        if (abs(pos_a - pos_b) != 1) {
            return false;
        }
    }
    return true;
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        string t;
        cin >> need_a[i] >> t >> t >> t >> t >> need_b[i];
    }

    // order_cow 初始就是字典序。按字典序枚举排列，第一个合法排列就是答案。
    do {
        if (check_order()) {
            for (int i = 0; i < COW_CNT; i++) {
                cout << order_cow[i] << '\n';
            }
            return 0;
        }
    } while (next_permutation(order_cow, order_cow + COW_CNT));

    return 0;
}

复杂度

最多枚举 8! 个排列，每个排列检查最多 7 条限制。由于 8 是常数，时间复杂度可以看作 $O(1)$ 。

只保存固定数量的名字和限制，空间复杂度为 $O(1)$ 。

总结

这题数据范围非常小，重点不是优化，而是利用字典序枚举。

只要初始名字数组按字典序排列，next_permutation 枚举到的第一个合法方案就是题目要求的答案。

目录

题意

思路

选择序列暴力

全排列枚举

代码

复杂度

总结