P3361 救生员问题 — C++ 区间覆盖与删除优化实现

好的，我们一起来分析并解决这个算法问题。这是一个经典的 **区间覆盖 + 删除一个区间后求最大覆盖长度** 问题，适合使用 **排序 + 前缀和/扫描线** 的优化思路，因为 N 最多可达 10^5，暴力枚举并每次重新计算会超时。 --- ## 🧠 问题理解 我们有 N 个区间（每个救生员的工作时间区间），需要删除一个区间，使得剩下的所有区间 **并集** 的覆盖总长度最大。 **注意：** - 区间是左闭右开？题目例子：`4 7` 覆盖 3 个单位，说明是左闭右开，即覆盖 `[start, end)`。 - 时间范围非常大（0 ~ 1e9），不能用数组直接标记。 - 结束时间都不相同，但开始时间可以相同。 --- ## 💡 解题思路 ### 1️⃣ 关键观察 - 如果删除一个区间，只会影响 **该区间独自贡献的部分**。 - 我们可以先求出所有区间的总覆盖长度，然后对于每个区间，计算它 **独自贡献的长度**，即去掉它之后会减少的长度。 - 最后取 `总覆盖长度 - min(单独贡献长度)`。 ### 2️⃣ 如何求“单独贡献长度”？ - 对所有区间按左端点排序。 - 扫描所有区间，维护当前覆盖的左右边界 `l, r`。 - 对于每个区间： - 如果它被完全包含在之前的覆盖中，则该区间单独贡献为 0。 - 否则它有一部分是新的覆盖，这部分就是它的单独贡献。 **优化方法**：先求总覆盖长度，再求每个区间的单独贡献长度。 --- ## ✅ 算法步骤 1. **输入并排序**：按开始时间升序，若相同按结束时间升序。 2. **计算总覆盖长度**： - 遍历排序后的区间，若当前区间与之前覆盖重叠或相接，则延长右边界；否则累加长度并更新左右边界。 3. **计算每个区间单独贡献长度**： - 使用类似方法，但需要知道该区间是否被完全覆盖，以及它独自延长的部分。 - 我们可以通过一次扫描，记录每个区间的前后关系，或者用两次扫描（前缀、后缀最远覆盖）来求。 4. **结果**： - 总覆盖长度 - 最小的单独贡献长度。 --- ## 🧑‍💻 C++ 实现 ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 100005; struct Interval { int l, r; } a[N]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; for (int i = 0; i < n; ++i) { cin >> a[i].l >> a[i].r; } // 按左端点排序，左相同按右排序 sort(a, a + n, [](const Interval &x, const Interval &y) { return x.l < y.l || (x.l == y.l && x.r < y.r); }); // 1. 计算总覆盖长度 ll total = 0; int cur_l = a[0].l, cur_r = a[0].r; for (int i = 1; i < n; ++i) { if (a[i].l <= cur_r) { cur_r = max(cur_r, a[i].r); } else { total += cur_r - cur_l; cur_l = a[i].l; cur_r = a[i].r; } } total += cur_r - cur_l; // 2. 计算每个区间的单独贡献长度 // 方法：用两个数组记录前缀最远覆盖右端点和后缀最远覆盖左端点 vector<int> pre_right(n), suf_left(n); // 前缀 int max_r = a[0].r; pre_right[0] = max_r; for (int i = 1; i < n; ++i) { max_r = max(max_r, a[i].r); pre_right[i] = max_r; } // 后缀 int min_l = a[n-1].l; suf_left[n-1] = min_l; for (int i = n-2; i >= 0; --i) { min_l = min(min_l, a[i].l); suf_left[i] = min_l; } // 计算每个人的单独贡献 ll min_alone = LLONG_MAX; for (int i = 0; i < n; ++i) { ll alone = 0; // 左边覆盖到的最右端 int left_r = (i == 0) ? a[i].l : max(a[i].l, pre_right[i-1]); // 右边覆盖到的最左端 int right_l = (i == n-1) ? a[i].r : min(a[i].r, suf_left[i+1]); if (left_r < right_l) { alone = right_l - left_r; } min_alone = min(min_alone, alone); } cout << total - min_alone << "\n"; return 0; } ``` --- ## 🔍 代码解释 - **排序**：按左端点排序，便于扫描。 - **总覆盖长度**：用贪心合并重叠区间。 - **单独贡献**： - 使用 `pre_right` 记录到当前位置为止能覆盖的最远右端点。 - 使用 `suf_left` 记录从当前位置往后能覆盖的最左起点。 - 对于第 i 个区间，它独自覆盖的部分 = 左边覆盖不到的部分与右边覆盖不到的部分的交集。 - **输出**：总覆盖长度 - 最小单独贡献。 --- ## ⏱ 复杂度分析 - **时间复杂度**：O(N log N)（排序）+ O(N)（扫描），满足 10^5 规模。 - **空间复杂度**：O(N)。 --- ## ⚠️ 常见陷阱与注意事项 - 注意区间是左闭右开，覆盖长度 = 右 - 左。 - 结束时间都不同，但开始时间可能相同，排序时要处理。 - 单独贡献可能为 0，此时删除它不影响总覆盖。 - 数据范围大，必须用 `long long`。 --- ## 📚 技术栈推荐与学习资源 - **推荐练习平台**：洛谷、Codeforces、AtCoder - **相关算法**：贪心、区间调度、扫描线 - **C++ 学习**：C++ Primer、cppreference.com --- ## 💡 开发建议 1. 遇到区间问题，优先考虑排序 + 扫描线。 2. 大数据范围下避免使用 `vector<bool>` 或 `map` 标记时间点。 3. 多练习“删除一个元素”类的问题，通常可以用前缀/后缀信息优化。 --- ######[AI写代码神器 | 1575点数解答 | 2026-07-14 20:13:59]