好斗的牛 题解

题目分析

我们有 $10^9$ 个连续的牛棚，需要选择一段连续的牛棚并将所有 $n$ 头牛放入其中，满足：任意两头牛之间不能进入彼此的攻击范围。

第 $i$ 头牛的攻击范围是 $(a_i, b_i)$，表示它左边 $a_i$ 个牛棚和右边 $b_i$ 个牛棚内不能出现其他牛。换句话说，如果把两头牛放在位置 $x$ 和 $y$（假设 $x<y$），那么：

• 对左边的牛（在 $x$）：右边 $b_{\text{左}}$ 个牛棚内不能有牛，因此需要 $y-x>b_{\text{左}}$。
• 对右边的牛（在 $y$）：左边 $a_{\text{右}}$ 个牛棚内不能有牛，因此需要 $y-x>a_{\text{右}}$。

两者综合起来，相邻两头牛之间的距离（位置差）至少为：

因为距离必须是整数，且 $d>\max (b_{\text{左}},a_{\text{右}})$ 等价于 $d \ge \max(b_{\text{左}}, a_{\text{右}}) + 1$。

由于我们要留下一段连续的牛棚，总长度就是第一头牛的位置到最后一头牛的位置之间的牛棚数。如果我们把牛尽量靠左放置，且第一头牛放在该段的第一个牛棚，那么总长度就等于：

其中 $d_i$ 是第 $i$ 头牛与第 $i-1$ 头牛之间的最小允许距离。

解题思路

问题的关键变成了：如何安排这 $n$ 头牛的排列顺序，使得总长度最小。

因为不同的排列会导致相邻牛的 $b_{\text{左}}$ 和 $a_{\text{右}}$ 不同，从而影响每段距离的大小。因此我们需要尝试所有可能的排列，计算对应的总长度，取最小值即可。

将总长度公式展开：

设排列为 $p_1, p_2, \dots, p_n$，则总长度：

因为 $1 + (n-1) = n$。

目标：最小化这个总长度。

算法说明

由于 $n \le 9$，数据规模非常小，可以直接使用 深度优先搜索（DFS） 枚举所有排列，计算每种排列的总长度，并更新最小值。

算法步骤：

1. 读入 $n$，以及每头牛的 $a_i, b_i$。
2. 使用 DFS 生成 $1 \sim n$ 的全排列，用一个数组记录当前排列。
3. 对于每个完整的排列，按照上述公式计算总长度，并更新全局最小值。
4. 输出最小值。

时间复杂度分析

• 全排列共有 $n!$ 种，对于每种排列，需要 $O(n)$ 的时间计算总长度。
• 当 $n=9$ 时，$9! = 362880$，计算量完全可以接受。
• 总时间复杂度为 $O(n! \cdot n)$，空间复杂度 $O(n)$。

参考代码

下面给出清晰实现的 C++ 代码，并附详细注释。

cpp
复制
1#include <bits/stdc++.h>
2using namespace std;
3
4int n;
5int a[10], b[10];          // 每头牛的 a 和 b
6int order[10];             // 当前排列的顺序（存放牛的编号）
7bool used[10];             // 标记某头牛是否已经排入
8int ans = INT_MAX;         // 最终答案，初始设为极大值
9
10// 计算当前排列下的最小牛棚长度
11void calculate() {
12    // 总长度初始为 n（每头牛自身占 1 个牛棚）
13    int len = n;
14    for (int i = 2; i <= n; ++i) {
15        int left_cow = order[i - 1];   // 左边的牛
16        int right_cow = order[i];      // 右边的牛
17        // 距离 = max(左边牛的 b, 右边牛的 a)，加上 1 后的累加已融入公式中
18        len += max(b[left_cow], a[right_cow]);
19    }
20    ans = min(ans, len);
21}
22
23// 深度优先搜索生成全排列，pos 表示当前正在安排第几头牛
24void dfs(int pos) {
25    if (pos > n) {         // 已经排完了 n 头牛
26        calculate();
27        return;
28    }
29    for (int i = 1; i <= n; ++i) {
30        if (!used[i]) {
31            used[i] = true;
32            order[pos] = i;
33            dfs(pos + 1);
34            used[i] = false;   // 回溯
35        }
36    }
37}
38
39int main() {
40    cin >> n;
41    for (int i = 1; i <= n; ++i) cin >> a[i];
42    for (int i = 1; i <= n; ++i) cin >> b[i];
43    
44    dfs(1);                 // 从第 1 个位置开始搜索
45    cout << ans << endl;
46    return 0;
47}

代码解释

• 全局数组：a 和 b 存储每头牛的攻击范围；order 存储当前排列中依次放置的牛的编号；used 标记某头牛是否已被使用。
• calculate() 函数：根据当前 order 计算总长度。根据前面的推导，总长度 = $n + \sum \max(b_{\text{prev}}, a_{\text{cur}})$，直接累加即可。
• dfs(pos) 函数：递归生成排列。pos 表示正在填充的位置，填满后调用 calculate()，并通过回溯尝试所有可能。
• main() 函数：读入数据，调用 dfs(1)，输出答案。

总结

本题把实际牛棚的放置问题转化为了一个排列最优化问题，通过分析相邻牛之间的约束，得到了简洁的距离公式。由于数据规模极小，直接枚举全排列即可轻松通过。这种“排列枚举 + 代价计算”的模式在竞赛入门题中非常常见，适合用来练习 DFS 和排列的组合应用。