把 n 头牛(有左右攻击范围)排进连续牛棚,使总跨度最小。
有 10⁹ 个牛棚一字排开。要把 n 头牛安置进去。第 i 头牛的攻击范围是 (aᵢ, bᵢ):若它的左边 aᵢ 个牛棚内或右边 bᵢ 个牛棚内有其他牛,它就会挑事。
要留下一段连续的牛棚(其余卖掉),使得能安置所有 n 头牛且无牛挑事。求最少需要留下多少个牛棚。
max(a_右牛 + 1, b_左牛 + 1)。全排列枚举相邻间隙跨度计算取最小值
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n;第二行 a₁…aₙ;第三行 b₁…bₙ |
| 输出 | 最少留下的牛棚数 |
| 数据范围 | 1 ≤ n ≤ 9 |
| 参数范围 | 1 ≤ aᵢ, bᵢ ≤ 10³ |
| 目标 | 最小跨度(连续牛棚数量) |
d > b_X、Y 要求 d > a_Y,所以 d ≥ max(b_X + 1, a_Y + 1)只有两种排列,都试一遍。
间距要求 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
d ≥ max(b₂ + 1, a₁ + 1) = max(3, 2) = 3
放置:p₂ = 1,p₁ = 4
跨度 = 4
跨度 4
最少 4 个牛棚 ✓
三种牛的参数呈"镜像":牛1(1,3)、牛2(2,2)、牛3(3,1)。共 6 种排列,我们只算最优的那一种。
牛 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
第 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(右) | 特点 |
|---|---|---|---|
| 1 | 1 | 3 | 右攻击范围大 |
| 2 | 2 | 2 | 左右对称 |
| 3 | 3 | 1 | 左攻击范围大 |
把"左攻击大的牛放右边、右攻击大的牛放左边",间距才最省
答案 7 ✓
max"的方向:左边那头牛贡献的是它的 b(右攻击范围),右边那头牛贡献的是它的 a(左攻击范围)。枚举 n! 种顺序,每种线性计算跨度,取最小
0…n−1 放进一个数组,用 next_permutation 遍历所有排列;对每个排列从左到右累加间距pos += max(b[left]+1, a[right]+1),最后跨度 = pos_end − 1 + 1。n ≤ 9 是题目给的最强提示:看到 9 就该想到全排列。dp[mask][last] 表示已放 mask 这些牛、最后一头是 last 时的最小左端位置
| 方案 | 复杂度(n = 9) | 代码量 |
|---|---|---|
| 全排列 | 约 3.3 × 10⁶ | 约 25 行 |
| 状压 DP | 约 4 × 10⁴ | 约 40 行 |
第一行输入 a 数组,第二行输入 b 数组,程序会枚举所有排列并找出最小跨度。
点按钮开始 →
#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 要求初始数组已升序。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
2 | 4 | 题面样例 1 |
3 | 7 | 题面样例 2(最优顺序 3 → 2 → 1) |
1 | 1 | 只有一头牛,1 个牛棚足够 |
2 | 3 | 间距 = max(1+1, 1+1) = 2 → 跨度 3 |
3 | 5 | 三头牛各隔 2:位置 1、3、5 → 跨度 5 |
next_permutation 需要初始有序,否则会漏掉排列。只需存 a、b 数组和一个排列数组。
✅ 约 330 万次操作,瞬间完成。n ≤ 9 这个"异常小"的范围就是题目的解法提示。
// 全排列枚举模板 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_permutation | n ≤ 9 的所有排列问题 |
| 相邻约束 | 只需满足相邻,远处自动满足 | 排列中的局部约束 |
| 数据范围即提示 | n 小 → 枚举 | 竞赛读题的第一反应 |
dp[mask][last] 表示"已经放了 mask 这些牛、最后一头是 last"时最右端位置的最小值,转移时枚举下一头牛即可,复杂度 O(2ⁿ × n²),n = 15 时约 700 万 ✓。"n 小用枚举、n 中用状压"是排列类问题的通用升级路线。)