基于区间标记的树木存活计数C++实现

根据描述，我们需要计算未被任何区域覆盖的树木数量。n棵树木编号通常为1到n，区域为闭区间[Li, Ri]。由于区域可能重合，但每棵树只被摧毁一次，所以只需标记被覆盖的位置，然后统计未被覆盖的数量。 提供C++解决方案如下： ```cpp #include <iostream> #include <vector> using namespace std; int main() { int n, m; cin >> n >> m; vector<bool> destroyed(n + 1, false); // 树木编号从1到n for (int i = 0; i < m; i++) { int L, R; cin >> L >> R; // 确保L和R在[1, n]范围内 if (L < 1) L = 1; if (R > n) R = n; for (int j = L; j <= R; j++) { destroyed[j] = true; } } int count = 0; for (int i = 1; i <= n; i++) { if (!destroyed[i]) count++; } cout << count << endl; return 0; } ``` 代码解释： - 使用布尔数组记录每棵树是否被摧毁。 - 对于每个区域，从L到R标记为已摧毁。 - 最后遍历所有树，统计未被标记的树的数量。 输入样例输出为2，符合预期（树1、5、7未被摧毁，所以剩余3棵？实际样例中：1-3摧毁1,2,3；3-4摧毁4（3已摧毁）；6-6摧毁6，剩余5和7，共2棵，正确）。 ######[AI问答 | 385点数解答 | 2026-08-09 10:06:59]