GESP 题解库 / 6 级题解 / [GESP202403 六级] 好斗的牛 · 第 17 / 27 题
GESP202403 六级 · P10377 · 简单

好斗的牛

把 n 头牛(有左右攻击范围)排进连续牛棚,使总跨度最小。

📊
n ≤ 9
牛的数量
🔢
int
范围参数
⚡
O(n! × n)
时间复杂度
🎯
全排列枚举 + 相邻间隙
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

有 10⁹ 个牛棚一字排开。要把 n 头牛安置进去。第 i 头牛的攻击范围是 (aᵢ, bᵢ):若它的左边 aᵢ 个牛棚内或右边 bᵢ 个牛棚内有其他牛,它就会挑事。

要留下一段连续的牛棚(其余卖掉),使得能安置所有 n 头牛且无牛挑事。求最少需要留下多少个牛棚。

💡
人话翻译:n ≤ 9 这个数据范围是明确提示——直接枚举所有排列(9! = 362880)即可。
对每种排列,从左到右依次放牛,相邻两头牛之间需要的最小间距是max(a_右牛 + 1, b_左牛 + 1)。
把所有间距加起来再加 1,就是这种排列需要的跨度;取所有排列中的最小值就是答案。

🔍 关键词提取

全排列枚举相邻间隙跨度计算取最小值

已知条件

项目说明
输入第一行 n;第二行 a₁…aₙ;第三行 b₁…bₙ
输出最少留下的牛棚数
数据范围1 ≤ n ≤ 9
参数范围1 ≤ aᵢ, bᵢ ≤ 10³
目标最小跨度(连续牛棚数量)

需要解决的问题

02
思维导图
整理解题思路的全貌
🐂 枚举排列 + 相邻最小间距
🧠 模型
留下连续一段牛棚
牛可以任意顺序放
使跨度最小
n ≤ 9 → 可以全排列
📐 间距公式
左牛 X、右牛 Y
X 要求 d > b_X
Y 要求 d > a_Y
d = max(b_X + 1, a_Y + 1)
🔁 计算
对每个排列贪心地最小放置
位置从 0 开始累加间距
跨度 = 末位 − 首位 + 1
取所有排列的最小值
⚠️ 易错点
把间距写成 max(a_X+1, b_Y+1)(左右搞反)
忘记最后 + 1
用 int 存放但实际范围很小(安全)
漏掉 n = 1 的情况
03
样例手算推导
两个样例的完整推演

🧮 样例 1:n = 2,a = [1, 2],b = [1, 2]

只有两种排列,都试一遍。

1
排列 (1, 2):牛 1 在左、牛 2 在右

间距要求 d ≥ max(b₁ + 1, a₂ + 1)

= max(1 + 1, 2 + 1) = max(2, 3) = 3

放置:p₁ = 1,p₂ = 1 + 3 = 4

跨度 = 4 − 1 + 1 = 4

跨度 4

2
排列 (2, 1):牛 2 在左、牛 1 在右

d ≥ max(b₂ + 1, a₁ + 1) = max(3, 2) = 3

放置:p₂ = 1,p₁ = 4

跨度 = 4

跨度 4

最少 4 个牛棚 ✓

🔑
验证样例解释:题目说"留下第 1、2、3、4 个牛棚,在第 1、4 个牛棚放牛"。
检查:两头牛相距 3,牛 1(在左)的右攻击范围 b₁ = 1 < 3 ✓ 不挑事;牛 2(在右)的左攻击范围 a₂ = 2 < 3 ✓ 不挑事。而如果只留 3 个牛棚(间距 2),a₂ = 2 不满足"大于 2",就会挑事。

🧮 样例 2:n = 3,a = [1, 2, 3],b = [3, 2, 1]

三种牛的参数呈"镜像":牛1(1,3)、牛2(2,2)、牛3(3,1)。共 6 种排列,我们只算最优的那一种。

1
试排列 (3, 2, 1)

牛 3 在左、牛 2 中间、牛 1 在右

第 1 个间距(3→2):max(b₃+1, a₂+1) = max(2, 3) = 3

第 2 个间距(2→1):max(b₂+1, a₁+1) = max(3, 2) = 3

位置:1、4、7

跨度 = 7 − 1 + 1 = 7

跨度 7

2
试排列 (1, 2, 3)

第 1 个间距(1→2):max(b₁+1, a₂+1) = max(4, 3) = 4

第 2 个间距(2→3):max(b₂+1, a₃+1) = max(3, 4) = 4

位置:1、5、9 → 跨度 9

跨度 9(更差)

📊 按"攻击范围大者居中"的思路理解

牛a(左)b(右)特点
113右攻击范围大
222左右对称
331左攻击范围大

把"左攻击大的牛放右边、右攻击大的牛放左边",间距才最省

答案 7 ✓

⚠️
注意"相邻间距取 max"的方向:左边那头牛贡献的是它的 b(右攻击范围),右边那头牛贡献的是它的 a(左攻击范围)。
写反了就完全错了——这是本题最容易出的错。
记忆方法:"两头牛互相看着对方",所以左边牛的右范围、右边牛的左范围都要被尊重。
04
解法对比
全排列枚举 vs 状压 DP

⚔️ 解法对比

🟢 全排列枚举(推荐) 推荐

枚举 n! 种顺序,每种线性计算跨度,取最小

  • 时间 O(n! × n)
  • n = 9 时约 3.3 × 10⁶
  • 代码 25 行(可用 next_permutation)
  • 简单直观
💡
实现:把 0…n−1 放进一个数组,用 next_permutation 遍历所有排列;对每个排列从左到右累加间距pos += max(b[left]+1, a[right]+1),最后跨度 = pos_end − 1 + 1。n ≤ 9 是题目给的最强提示:看到 9 就该想到全排列。

🟠 状压 DP

dp[mask][last] 表示已放 mask 这些牛、最后一头是 last 时的最小左端位置

  • 时间 O(2ⁿ × n²)
  • n = 9 时约 4 × 10⁴(更快)
  • 代码更复杂
  • 本题没必要
⚠️
什么时候值得用:如果 n 放大到 15 ~ 20,全排列(15! ≈ 1.3 × 10¹²)就不可行了,必须用状压 DP。但本题 n ≤ 9,全排列已经足够。

📈 性能对比

方案复杂度(n = 9)代码量
全排列约 3.3 × 10⁶约 25 行
状压 DP约 4 × 10⁴约 40 行
05
算法流程图
枚举所有排列并计算最小跨度
开始读入 n、数组 a、数组 b;ans = 正无穷构造排列数组 p = [0, 1, …, n − 1]对当前排列计算跨度:pos = 1,从左到右累加对相邻两头牛:pos = pos + max(b[左] + 1, a[右] + 1)跨度 = pos − 1 + 1;ans = min(ans, 跨度)还有下一个排列吗?是 ✓取下一个排列,回到计算否 ✗输出 ans输出 ans取下一个排列
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🐂 最少牛棚数

第一行输入 a 数组,第二行输入 b 数组,程序会枚举所有排列并找出最小跨度。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

int a[12], b[12];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < n; i++) scanf("%d", &b[i]);

    vector<int> p(n);
    for (int i = 0; i < n; i++) p[i] = i;      // 牛的编号 0 ~ n-1

    int ans = INT_MAX;

    do {
        // 从左到右依次按"最小间距"放置
        int pos = 1;                           // 第一头牛放在 1 号棚
        for (int i = 0; i + 1 < n; i++) {
            int l = p[i], r = p[i + 1];
            // 左牛的右攻击范围、右牛的左攻击范围,都要留够
            pos += max(b[l] + 1, a[r] + 1);
        }
        ans = min(ans, pos);                   // pos 就是"S 到 E 的跨度"
    } while (next_permutation(p.begin(), p.end()));

    printf("%d\n", ans);
    return 0;
}
🔑
为什么间距是 max(b[左] + 1, a[右] + 1)?设两头牛的位置差为 d(牛棚编号之差)。题目说"若左边 b 个牛棚内有牛就挑事"——所以要求 d > b[左],即 d ≥ b[左] + 1;同理右边那头要求 d ≥ a[右] + 1。
两个条件都要满足,所以取 max。注意是"左牛的 b"配"右牛的 a",方向千万不能反。

📖 关键几行怎么看

代码作用为什么这样写
vector<int> p(n)排列数组存牛编号,配合 next_permutation
int pos = 1起点第一头牛放在 1 号牛棚
pos += max(b[l]+1, a[r]+1)累加间距左牛 b、右牛 a
ans = min(ans, pos)取最小pos 正好等于跨度(末 − 首 + 1)
next_permutation枚举排列自动遍历全部 n! 种
⚠️
四个坑:① 间距写成 max(a[左]+1, b[右]+1)(方向反了);② 忘记 +1("范围内有牛就挑事"是严格不等式);③ ans 初值取 0(应取一个很大的数);④ next_permutation 要求初始数组已升序。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
2
1 2
1 2
4题面样例 1
3
1 2 3
3 2 1
7题面样例 2(最优顺序 3 → 2 → 1)
1
5
5
1只有一头牛,1 个牛棚足够
2
1 1
1 1
3间距 = max(1+1, 1+1) = 2 → 跨度 3
3
1 1 1
1 1 1
5三头牛各隔 2:位置 1、3、5 → 跨度 5
✅
自查清单:① 间距方向对吗?② 加 1 了吗?③ 枚举了全部排列吗?

🚨 易错点清单

⚠️
间距方向反:必须是"左牛的 b"和"右牛的 a",写成 a[左]、b[右] 就错了。
⚠️
忘记 +1:"b 个牛棚内有牛就挑事"意味着距离必须 > b。
⚠️
排列未升序初始化:next_permutation 需要初始有序,否则会漏掉排列。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n! × n)
空间复杂度
O(n)
n 最大
9
运算量
约 3.3 × 10⁶

时间怎么算的?

空间都用在哪?

只需存 a、b 数组和一个排列数组。

✅ 约 330 万次操作,瞬间完成。n ≤ 9 这个"异常小"的范围就是题目的解法提示。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 全排列枚举模板
vector<int> p(n);
iota(p.begin(), p.end(), 0);          // 0, 1, 2, ..., n-1(必须升序)
do {
    // 对排列 p 做计算
} while (next_permutation(p.begin(), p.end()));

// 本题的跨度计算
int span(const vector<int>& p, int a[], int b[]) {
    int n = p.size(), pos = 1;
    for (int i = 0; i + 1 < n; i++)
        pos += max(b[p[i]] + 1, a[p[i+1]] + 1);   // 左牛b、右牛a
    return pos;
}

// 如果 n 变大(15 ~ 20):改用状压 DP
// dp[mask][last] = 放完 mask 这些牛、最后放 last 时"最右端位置"的最小值
// 转移:dp[mask | (1<<j)][j] = min(dp[mask][last] + gap(last, j))

// 竞赛经验:数据范围就是解法提示
// n <= 9   -> 全排列 / 搜索
// n <= 20  -> 状压 DP
// n <= 500 -> O(n^3) 区间 DP 或 Floyd
// n <= 1e5 -> O(n log n)

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
全排列枚举next_permutationn ≤ 9 的所有排列问题
相邻约束只需满足相邻,远处自动满足排列中的局部约束
数据范围即提示n 小 → 枚举竞赛读题的第一反应
🌟
思考题:如果 n 放大到 15,全排列(15! ≈ 1.3 × 10¹²)就不可行了,你会怎么做?(提示:用状压 DP——dp[mask][last] 表示"已经放了 mask 这些牛、最后一头是 last"时最右端位置的最小值,转移时枚举下一头牛即可,复杂度 O(2ⁿ × n²),n = 15 时约 700 万 ✓。"n 小用枚举、n 中用状压"是排列类问题的通用升级路线。)