GESP C++三级算法实战：NOIP 2005校门外的树问题解析

题目描述

某校大门外有一条长度为 l 米的马路，路上每隔 1 米种有一棵树。我们可以将马路视为一个数轴，从 0 到 l 的每个整数点都种有一棵树。现在，由于建设地铁的需要，一些区域内的树木需要被移走。这些区域用起始点和终止点表示，坐标均为整数，且区域之间可能重叠。任务是将指定区域内的树（包括区域端点处的树）移走后，计算马路上剩余树木的数量。

输入格式

第一行包含两个整数 l 和 m，分别表示马路长度和区域数量。接下来 m 行，每行两个整数 a 和 b，表示一个区域的起始和终止坐标。

输出格式

输出一个整数，表示移走树木后马路上剩余的树木数量。

输入输出样例

输入 #1：

500 3
150 300
100 200
470 471

输出 #1：

298

数据范围

• 对于部分数据，保证区域之间没有重合。
• 对于 100% 的数据，保证 1 ≤ l ≤ 10000，1 ≤ m ≤ 100，0 ≤ a ≤ b ≤ l。

解题思路

这道题是经典的区间覆盖问题，适合用一维数组来模拟马路上的树木状态。首先，创建一个长度为 l+1 的数组，初始化所有位置为有树（例如标记为1）。然后，对于每个需要移除树木的区域 [a, b]，将区间内所有位置标记为无树（值为0）。最后，遍历数组统计标记为有树的位置数量即可。这种方法直观易懂，特别适合初学者理解算法与数据结构中数组的基本应用。

复杂度分析：时间复杂度约为 O(∑(b-a+1))，其中每个区间长度影响循环次数；空间复杂度为 O(l)，用于存储数组。

示例代码

#include <iostream>
#include <array>

std::array<int, 10005> tree_status; // 数组记录树木状态，1表示有树，0表示无树

int main() {
    int l, m;
    std::cin >> l >> m;
    tree_status.fill(1); // 初始化所有位置有树

    for (int i = 0; i < m; i++) {
        int a, b;
        std::cin >> a >> b;
        for (int j = a; j <= b; j++) {
            tree_status.at(j) = 0; // 移除区间内的树木
        }
    }

    int count = 0;
    for (int i = 0; i <= l; i++) {
        if (tree_status.at(i)) {
            count++; // 统计剩余树木
        }
    }

    std::cout << count;
    return 0;
}

代码使用 std::array 确保数组大小固定，在数据范围内高效运行。通过这个练习，可以巩固C++数组操作和基础算法思维，为更高阶的编程挑战打下基础。