基于布尔数组标记法求解重叠区域摧毁后的剩余树木数量

根据题意，需要计算在多个可能重叠的区域被摧毁后，剩余完好的树木数量。由于区域可能重合，每棵树只被摧毁一次，因此只需统计所有被摧毁树木的并集大小，然后用总树木数减去该并集大小。 一种高效且直观的方法是使用一个布尔数组标记每棵树是否被摧毁，最后统计未被标记的数量。考虑到n<100，这种方法的复杂度O(n*m)完全可行。 以下是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; // 确保R不超过n，L不小于1（题目保证合法，但可加保护） if (L < 1) L = 1; if (R > n) R = n; 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; } ``` 这个解法直接遍历每个区域的树木并标记，最后统计未标记的数量。由于每棵树只会被标记一次（因为重复区域标记为true但不会改变值），所以结果正确。时间复杂度O(n*m)，空间复杂度O(n)。 ######[AI问答 | 368点数解答 | 2026-08-02 15:40:01]