用C++计算树木被摧毁后剩余棵数

好的，我们先理解下问题：有n棵树排成一列，机器人们摧毁了m个连续区域内的树木，不同区域可能重叠，但每棵树只会被摧毁一次。要求计算最终还剩下几棵完好的树木。 --- ### ✅ 解题思路 我们可以创建一个长度为 `n+1` 的布尔数组，标记哪些树被摧毁。 对于每个区域 `[Li, Ri]`，将对应范围内的树标记为已摧毁。 最后统计未被标记的树的数量。 由于 `n < 100`，这种直接的暴力方法速度足够。 --- ### ✅ C++ 代码实现 ```cpp #include <iostream> #include <vector> using namespace std; int main() { int n, m; cin >> n >> m; vector<bool> destroyed(n + 1, false); // 下标从1开始 for (int i = 0; i < m; i++) { int L, R; cin >> 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; } ``` --- ### ✅ 代码解析 - 使用 `vector<bool> destroyed(n+1, false)` 来表示每棵树是否被摧毁，初始为 `false`。 - 对于每个区域 `[Li, Ri]`，遍历 `j` 从 `Li` 到 `Ri`，标记 `destroyed[j] = true`。 - 最后遍历所有树，计数未被摧毁的树。 --- ### ✅ 测试样例 输入： ``` 7 3 1 3 3 4 6 6 ``` 运行过程： - 初始：所有树未摧毁 - 区域1：摧毁树1,2,3 - 区域2：摧毁树3,4（树3已摧毁，无影响） - 区域3：摧毁树6 最终被摧毁的树：1,2,3,4,6 剩余：5,7 → 共2棵 输出： ``` 2 ``` 与题目示例一致。 --- ### ✅ 复杂度分析 - 时间复杂度：O(n * m)，最坏情况 n=99, m=99，约 9801 次操作，非常适合题目限制。 - 空间复杂度：O(n)，用于布尔数组。 --- ######[AI问答 | 560点数解答 | 2026-06-06 14:35:04]