区间覆盖问题：布尔数组法与区间合并法求剩余树木数量

好的，我们来一步步分析并解决这个问题。 ## 🌲 问题理解 我们有一排树，编号从 `1` 到 `n`。 有 `m` 个机器人分别摧毁了某些连续区域的树，每个区域用 `[Li, Ri]` 表示（包括两端）。 注意：**区域可能重叠**，但每棵树**只被摧毁一次**（所以重叠不会重复计算）。 要求输出**最终剩下的完好无损的树木棵数**。 **输入格式**： - 第一行：`n m` - 接下来 `m` 行：每行 `Li Ri` **输出**： - 一个整数：剩余的树木数量 **样例**： ``` 输入： 7 3 1 3 3 4 6 6 输出： 2 ``` 解释：总共7棵树，摧毁了1,2,3,4,6，剩下5和7，共2棵。 --- ## 💡 解题思路 ### 方法一：布尔数组标记法（推荐，简单高效） 1. 创建一个长度为 `n+1` 的布尔数组 `destroyed`（索引从1开始），初始化为 `false`。 2. 对于每个区域 `[Li, Ri]`，遍历 `j` 从 `Li` 到 `Ri`，将 `destroyed[j]` 设为 `true`。 3. 统计 `destroyed` 中为 `false` 的个数（即未摧毁的树）。 4. 输出统计结果。 **时间复杂度**： - 最坏情况下，每个区域长度可能为 n，总复杂度为 O(m * n)，但 n < 100，完全可行。 **空间复杂度**：O(n) --- ### 方法二：区间合并法（进阶，适合大数据） 如果 n 非常大（如 10^9），则需要用区间合并算法： 1. 将所有区间按左端点排序。 2. 合并重叠区间，得到不重叠的摧毁区间。 3. 计算总摧毁树木数 = 各区间长度之和。 4. 剩余树木 = n - 总摧毁数。 这种方法更高效，但从本题数据规模看，方法一已经足够。 --- ## ✍️ C++ 代码实现（方法一） ```cpp #include <iostream> #include <vector> using namespace std; int main() { int n, m; cin >> n >> m; // 布尔数组标记是否被摧毁，索引从1开始 vector<bool> destroyed(n + 1, false); for (int i = 0; i < m; i++) { int L, R; cin >> L >> R; // 将区间 [L, R] 内的所有树标记为已摧毁 for (int j = L; j <= R; j++) { destroyed[j] = true; } } // 统计未被摧毁的树 int remaining = 0; for (int i = 1; i <= n; i++) { if (!destroyed[i]) { remaining++; } } cout << remaining << endl; return 0; } ``` --- ## 🧪 样例测试 输入： ``` 7 3 1 3 3 4 6 6 ``` 运行过程： - destroyed数组初始全为false - 区域1：1~3 → true - 区域2：3~4 → true（3已被标记，不变） - 区域3：6~6 → true - 最终destroyed[1..7] = [T,T,T,T,F,T,F] - 未摧毁的：5,7 → 2 输出： ``` 2 ``` 与题目一致 ✅ --- ## ⚠️ 开发建议与常见陷阱 ### 1. **数组越界** - 一定要用 `n+1` 长度的数组，且访问从 1 到 n，避免越界。 ### 2. **每棵树只被摧毁一次** - 题目已保证，所以直接用布尔标记即可，不需要考虑重复计数。 ### 3. **输入读取** - 使用 `cin` 或 `scanf` 均可，注意 `m` 行输入格式正确。 ### 4. **性能** - n < 100，即使 m 很大（比如 100），最坏也只需 100*100 = 10^4 次操作，完全没问题。 ### 5. **扩展思考** - 如果 n 很大（比如 10^9），就无法用布尔数组了，需要用区间合并法。这里也提供一个简要思路，但不作为本题要求。 --- ## 🚀 进阶：区间合并法简介（仅供拓展） ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n, m; cin >> n >> m; vector<pair<int, int>> intervals(m); for (int i = 0; i < m; i++) { cin >> intervals[i].first >> intervals[i].second; } // 按左端点排序 sort(intervals.begin(), intervals.end()); int totalDestroyed = 0; int curL = intervals[0].first, curR = intervals[0].second; for (int i = 1; i < m; i++) { if (intervals[i].first <= curR + 1) { // 区间重叠，合并 curR = max(curR, intervals[i].second); } else { // 不重叠，计算当前区间长度 totalDestroyed += (curR - curL + 1); curL = intervals[i].first; curR = intervals[i].second; } } // 加上最后一个区间 totalDestroyed += (curR - curL + 1); cout << n - totalDestroyed << endl; return 0; } ``` 适用场景：n 极大，无法使用数组。 --- ######[AI写代码神器 | 1310点数解答 | 2026-06-06 20:58:20]