KKT 数组 204 校门外的树 - C++ 代码实现与算法解析 - 常规

KKT 数组 204 校门外的树 - C++ 代码实现与算法解析

问题描述:

某校大门外长度为 L 的马路上有一排树，每两棵相邻的树之间的间隔都是1米。

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

输入描述:

第一行有两个整数 L 和 M，L 代表马路的长度，M 代表区域的数目，L 和 M 之间用一个空格隔开。

接下来的 M 行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。

输出描述:

包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。

用例输入 1:

用例输出 1:

C++ 代码实现:

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int L, M;
    cin >> L >> M;
    vector<int> trees(L + 1, 1); // 初始化马路上的树，默认都存在

    for (int i = 0; i < M; i++) {
        int start, end;
        cin >> start >> end;
        for (int j = start; j <= end; j++) {
            trees[j] = 0; // 将区域内的树移走
        }
    }

    int remaining = 0;
    for (int i = 0; i <= L; i++) {
        remaining += trees[i]; // 统计剩余的树的数量
    }

    cout << remaining << endl;

    return 0;
}

算法解析:

初始化: 使用一个长度为 L+1 的 vector<int> 数组 trees 来模拟马路，数组元素初始值为 1，表示每棵树都存在。
移除区域内的树: 遍历每个区域，对于每个区域的起始点 start 和终止点 end，将 trees 数组中对应位置的元素设为 0，表示将区域内的树移除。
统计剩余的树: 遍历 trees 数组，统计所有元素值为 1 的元素数量，即为剩余的树的数量。

代码解释:

vector<int> trees(L + 1, 1); 初始化一个长度为 L+1 的数组 trees，并将其所有元素初始化为 1，表示马路上的所有树都存在。
for (int j = start; j <= end; j++) { trees[j] = 0; } 遍历区域内的所有树，将对应位置的 trees 数组元素设为 0，表示移除树。
remaining += trees[i]; 统计 trees 数组中值为 1 的元素数量，即为剩余的树的数量。

总结:

本题使用简单的数组模拟马路，并通过遍历区域将区域内的树移除，最终统计剩余的树的数量。代码简洁易懂，算法效率较高。