布尔类型数组

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

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

输入描述:
第一行有两个整数：L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。
输出描述:
包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。
示例1
输入
复制
500 3
150 300
100 200
470 471
输出
复制
298
备注:
对于20%的数据，区域之间没有重合的部分；
对于其它的数据，区域之间有重合
以下是使用 C++ 解决上述问题的代码：
cpp
#include
#include
#include
using namespace std;

int main() {
    int L, M;
cin >> L;
cin >> M;
    // 使用布尔数组来标记树是否被移走，初始时都为false表示树都在
    vector trees(L + 1, false);
    for (int i = 0; i < M; i++) {
        int start, end;
cin >> start;
cin >> end;
        for (int j = start; j <= end; j++) {
            trees[j] = true;
        }
    }
    int count = 0;
    for (int i = 0; i <= L; i++) {
        if (!trees[i]) {
            count++;
        }
    }
    cout << count << endl;
    return 0;
}
代码解释
读取输入数据：
首先从标准输入读取两个整数 L 和 M，分别表示马路的长度和区域的数目。
这里限定了 1 <= L <= 10000 和 1 <= M <= 100，确保输入数据在合理的范围内。
初始化表示树的状态的数组：
创建一个 vector 类型的数组 trees，长度为 L + 1（因为包含数轴上 0 到 L 这 L + 1 个位置），并初始化为 false，表示初始时所有的树都在，没有被移走。
标记要移走的树：
通过一个循环读取每个区域的起始点和终止点坐标（start 和 end）。
对于每个区域，再通过一个内层循环将该区域内（从 start 到 end，包含端点）对应的 trees 数组中的元素标记为 true，表示这些位置的树要被移走。
统计剩余树的数量：
遍历整个 trees 数组，通过一个循环从 0 到 L 检查每个位置。
如果某个位置对应的数组元素为 false，说明该位置的树没有被移走，将计数器 count 加 1。
输出结果：
最后将统计得到的剩余树的数量 count 输出到标准输出。
这样，代码就实现了根据输入的马路长度、区域信息，计算出移走指定区域内的树后马路上剩余树的数量的功能。
不过，上述代码还可以进一步优化。因为题目中提到区域之间可能有重合部分，上述代码在标记要移走的树时，对于重合区域会进行多次重复标记操作，虽然结果正确，但效率稍低。可以先对输入的区域按照起始点坐标进行排序，然后在标记时避免重复处理重合区域

布尔类型数组

全站热榜