C++实现地铁施工后剩余树木数量计算（区间合并法）

好的，我们来一起解决这个“移树”问题。这是一个经典的**区间合并与计数**问题，非常适合用来练习算法思维和C++基础。 --- ## 🧩 问题分析 - 马路长度 `l`，共有 `l+1` 棵树（从0到l）。 - 给出 `m` 个区域 `[u, v]`，这些区域中的树都会被移走。 - 区域可能有重叠，需要避免重复计数。 - 最后输出剩余的树的数量。 **核心思路**： 我们可以把每个区域看成数轴上的一个区间，先将所有区间**按照起点排序**，然后**合并重叠区间**。合并后，每个区间内的树都会被移走。用总树数减去所有合并后区间内包含的树的总数。 --- ## 🚀 实现步骤 1. **读取输入**：读取 `l` 和 `m`，以及 `m` 个区间 `[u, v]`。 2. **排序区间**：按起点 `u` 升序排序。 3. **合并区间**：遍历排序后的区间，如果当前区间与上一个区间重叠或相连，则合并；否则，将上一个区间计入移走的树的数量。 4. **计算剩余树**：总树数 = `l + 1`，减去所有合并后区间内树的数量（区间长度 + 1）。 5. **输出结果**。 --- ## 💻 完整代码（C++） ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int l, m; cin >> l >> m; vector<pair<int, int>> intervals(m); for (int i = 0; i < m; ++i) { cin >> intervals[i].first >> intervals[i].second; } // 1. 按起点排序 sort(intervals.begin(), intervals.end()); // 2. 合并区间并计算移除的树的数量 int removed = 0; int cur_start = intervals[0].first; int cur_end = intervals[0].second; for (int i = 1; i < m; ++i) { if (intervals[i].first <= cur_end + 1) { // 有重叠或相连，合并 cur_end = max(cur_end, intervals[i].second); } else { // 不重叠，结算当前区间 removed += (cur_end - cur_start + 1); cur_start = intervals[i].first; cur_end = intervals[i].second; } } // 处理最后一个区间 removed += (cur_end - cur_start + 1); // 3. 输出剩余树的数量 cout << (l + 1 - removed) << endl; return 0; } ``` --- ## 🔍 关键点解释 ### 📌 为什么合并区间时用 `<= cur_end + 1`？ - 因为区间 `[1,3]` 和 `[4,6]` 是**相邻**的，虽然没有重叠，但合并后相当于移走 `[1,6]` 的树，结果与分别计算相同。为了简化，我们直接合并相邻区间。 ### 📌 排序的重要性 - 如果不排序，合并算法会出错。排序后，我们只需一次遍历即可完成合并。 ### 📌 区间长度的计算 - 区间 `[u, v]` 包含 `v - u + 1` 棵树。 --- ## ⚙️ 复杂度分析 - **时间复杂度**：`O(m log m)`，主要来自排序。 - **空间复杂度**：`O(m)`，存储区间。 --- ## 💡 进阶与扩展 | 场景 | 建议 | |------|------| | 数据范围很大（如 `l` 达到 10^9） | 用区间合并法，不要用布尔数组 | | 需要多次查询 | 可以构建线段树或差分数组 | | 区域可能不相邻但连续 | 合并时注意相邻区间（`<= cur_end + 1`） | | 输入可能包含无效数据 | 添加简单的输入校验 | --- ## 🧰 开发建议 1. **命名清晰**：变量名如 `cur_start` 比 `s` 更容易理解。 2. **边界测试**：测试 `l=0`、`m=0`、区域完全覆盖马路等情况。 3. **使用 `pair`**：C++ 的 `pair` 非常适合表示区间，排序时自动按 `first` 排序。 4. **刷题习惯**：先在纸上模拟小数据，再写代码。 --- ## ❓ 常见问题（FAQ） - **Q**：如果区域有嵌套（如 `[1,10]` 和 `[2,5]`）会怎样？ **A**：合并时会被正确合并为一个区间 `[1,10]`。 - **Q**：为什么不用布尔数组标记？ **A**：如果 `l` 很大（比如 10^7 以上），布尔数组会消耗过多内存且速度慢。区间合并法更高效。 - **Q**：输入里区域顺序乱序怎么办？ **A**：排序后处理，无需担心。 --- ######[AI写代码神器 | 1171点数解答 | 2026-05-23 15:09:22]