P1047 [NOIP2005 普及组] 校门外的树

题目：

某校大门外长度为 ll 的马路上有一排树，每两棵相邻的树之间的间隔都是 11 米。我们可以把马路看成一个数轴，马路的一端在数轴 00 的位置，另一端在 ll 的位置；数轴上的每个整数点，即 0,1,2,…,l0,1,2,…,l，都种有一棵树。

由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。

分析：

1. 题目分析：
   • 已知马路长度 L，以及多个需要移走树的区间，每个区间由起始点和终止点表示，要计算移走这些区间内的树后剩余树的数量。
2. 代码实现思路：
   • 可以使用一个布尔数组（bool）来标记每棵树是否被移除。遍历所有的区间，将区间内的树在数组中对应的位置标记为已移除（true）。最后统计数组中未被标记（false）的元素个数，即为剩余树的数量。
3. 代码：
4. 

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int l,m; //  输入马路长度l 输入要移走树的区域数量m
    cin >> l>>m;
    vector<bool> re(l + 1, false); 
     // 定义一个布尔数组，用于标记每棵树是否被移除，初始都为false（未移除）
    for (int i = 0; i < m; i++) {
        int start, end;// 输入每个区域的起始点和终止点
        cin >> start >> end;
        for (int j = start; j <= end; j++) {
            // 将该区域内的树标记为已移除
            re[j] = true;
        }
    }
    int count = 0;
    for (int i = 0; i <= l; i++) {
        if (!re[i]) {
            // 统计未被移除的树的数量
            count++;
        }
    }
    cout << count << endl;
    return 0;
}

代码解释：

1.首先，通过cin读取马路长度l和要移走树的区域数量m。

2.然后创建一个长度为l + 1的布尔数组removed，用于标记每棵树是否被移除，初始值都为false，表示所有树都未被移除。

3.接着通过两层循环，外层循环m次，每次读取一个区域的起始点start和终止点end，内层循环将该区域内的树在removed数组中对应的位置标记为true，表示已移除。

4.最后，遍历removed数组，统计值为false的元素个数，即剩余树的数量，并输出结果。

                                                                                                                        C++编程研习社

                                                                                                                                        Hank