题目链接

校门外的树

题目描述

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

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

输入描述:

  • 第一行输入两个整数 L 和 M，用空格隔开，表示马路的长度和地铁施工区域数。
  • 接下来 M 行，每行输入两个整数 u 和 v，用空格隔开，表示一个施工区域的起始点和终止点坐标。

输出描述:

  • 输出一个整数，表示移除所有施工区域内（包括端点）的树后，剩余的树的总棵树。

示例说明:

  • 输入: 
    500 3
150 300
100 200
470 471
  • 输出: 298
  • 说明:
    • 马路总长 500，所以初始有 500 + 1 = 501 棵树。
    • 三个区域 [150, 300], [100, 200], [470, 471] 内的树要被移除。
    • 由于区域 [150, 300] 和 [100, 200] 有重合部分 [150, 200]，直接计算各区段树木数量然后相加再减去会很复杂。
    • 更简单的方法是标记所有被移除的树，然后统计未被标记的树的数量。

解题思路

本题的核心是处理区间重叠问题。由于马路总长度 L 的最大值（10000）不是特别大，我们可以使用一个数组来模拟马路上的每一棵树的状态，这是一种非常直观且易于实现的方法。

思路：标记法 (数组模拟)

  1. 创建马路模型: 我们可以创建一个大小为 L+1 的数组（比如布尔类型或整型），road[i] 用来表示在位置 i 的树的状态。例如，road[i] = 1 (或 true) 表示树存在，road[i] = 0 (或 false) 表示树被移除。

  2. 初始化:

    • 马路的总长度是 L，但树是种在整数点上的，从 0 到 L，所以总共有 L+1 个位置。
    • 我们创建一个大小为 L+1 的数组，并将所有元素初始化为 1，表示所有位置最初都有树。
    • 初始的树木总数 total_trees 就是 L+1。

  3. 处理施工区域:

    • 我们循环 M 次，每次读入一个施工区域的起点 u 和终点 v。
    • 对于每个区域 [u, v]，我们再用一个循环，遍历从 u 到 v 的所有位置。
    • 在遍历过程中，我们将对应位置的树标记为"已移除"。即，如果 road[i] 的值还是 1，我们就把它设置为 0，并从总树数 total_trees 中减一。如果 road[i] 已经为 0，说明这棵树因为与其他区域重叠已经被移除过了，我们就不需要重复计数。

  4. 输出结果:

    • 当所有 M 个区域都处理完毕后，变量 total_trees 中存储的就是最终剩余的树木数量。直接输出即可。

这个方法巧妙地避开了复杂的区间合并计算，通过空间换时间，将问题简化为简单的标记和计数。

思路二：差分数组 (优化)

"标记法"的思路虽然直观，但其时间复杂度和区间长度有关。当 M 和 L 都很大时，内层循环会执行很多次，效率不高。我们可以使用 差分数组 的思想来优化区间的标记过程。

  1. 差分思想: 差分是前缀和的逆运算。我们可以创建一个差分数组 diff，用它来记录每个点相对于前一个点的变化量。

    • diff 数组的作用是：对原数组一个区间 [u, v] 里的所有元素都加上一个数 x，只需要在差分数组上做两次修改：diff[u] += x 和 diff[v+1] -= x。
    • 最后，通过计算差分数组的前缀和，就可以还原出被修改后的原数组。

  2. 应用于本题:

    • 我们可以用一个数组 coverage 来记录每个位置被多少个施工区域所覆盖。初始时，所有位置的覆盖次数都是0。
    • 我们想对每个施工区域 [u, v]，将 coverage 数组在 [u, v] 区间内的所有元素都 +1。
    • 我们可以创建 coverage 数组对应的差分数组 diff，其大小为 L+2（因为 v 最大可以是 L，v+1就需要 L+1 的索引，数组大小需要 L+2）。
    • 对于每个区域 [u, v]，我们执行 diff[u]++ 和 diff[v+1]--。
    • 处理完所有 M 个区域后，我们对 diff 数组求前缀和，来得到最终的 coverage 数组。
      • coverage[i] = coverage[i-1] + diff[i] (其中 coverage[-1]=0)。
    • coverage[i] 的值就代表了位置 i 的树被多少个施工区域覆盖。

  3. 统计结果:

    • 在得到 coverage 数组后，我们遍历从 0 到 L 的每个位置。
    • 如果 coverage[i] == 0，说明这个位置没有被任何施工区域覆盖，这里的树还存在。
    • 我们统计 coverage[i] == 0 的位置个数，就是最终剩余的树木数量。

算法步骤概览:

  • 读入 L 和 M。
  • 创建一个大小为 L+1 的数组 road，全部初始化为 1。
  • for m from 1 to M:
    • 读入区域 u, v。
    • for i from u to v:
      • 将 road[i] 标记为 0 (表示移除)。
  • count = 0
  • for i from 0 to L:
    • 如果 road[i] 是 1，则 count++。
  • 输出 count。

代码

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

int main() {
    int l, m;
    cin >> l >> m;
    
    // 创建一个大小为 l+1 的数组，true 表示有树
    vector<bool> road(l + 1, true);
    
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        // 将区域 [u, v] 内的树标记为 false (移除)
        for (int j = u; j <= v; ++j) {
            road[j] = false;
        }
    }
    
    int remaining_trees = 0;
    // 统计还剩多少棵树
    for (int i = 0; i <= l; ++i) {
        if (road[i]) {
            remaining_trees++;
        }
    }
    
    cout << remaining_trees << endl;
    
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int l = sc.nextInt();
        int m = sc.nextInt();
        
        // 创建布尔数组，true 表示有树
        boolean[] road = new boolean[l + 1];
        for (int i = 0; i <= l; i++) {
            road[i] = true;
        }
        
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            // 标记要移除的树
            for (int j = u; j <= v; j++) {
                road[j] = false;
            }
        }
        
        int remainingTrees = 0;
        // 统计剩余的树
        for (int i = 0; i <= l; i++) {
            if (road[i]) {
                remainingTrees++;
            }
        }
        
        System.out.println(remainingTrees);
    }
}

l, m = map(int, input().split())

# 创建列表，1 表示有树
road = [1] * (l + 1)

for _ in range(m):
    u, v = map(int, input().split())
    # 标记要移除的树
    for i in range(u, v + 1):
        road[i] = 0

# 统计剩余的树
# sum()可以直接计算列表中所有元素的和
remaining_trees = sum(road)

print(remaining_trees)

方法二：差分数组

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int l, m;
    cin >> l >> m;
    
    // 差分数组，大小为 l+2 以处理 v=l 的情况 (v+1)
    vector<int> diff(l + 2, 0);
    
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        diff[u]++;
        diff[v + 1]--;
    }
    
    int remaining_trees = 0;
    int coverage = 0; // 当前点的覆盖数
    
    // 通过前缀和计算每个点的覆盖数并统计
    for (int i = 0; i <= l; ++i) {
        coverage += diff[i];
        if (coverage == 0) {
            remaining_trees++;
        }
    }
    
    cout << remaining_trees << endl;
    
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int l = sc.nextInt();
        int m = sc.nextInt();
        
        // 差分数组
        int[] diff = new int[l + 2];
        
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            diff[u]++;
            diff[v + 1]--;
        }
        
        int remainingTrees = 0;
        int coverage = 0; // 当前点的覆盖数
        
        // 通过前缀和还原覆盖数组并统计
        for (int i = 0; i <= l; i++) {
            coverage += diff[i];
            if (coverage == 0) {
                remainingTrees++;
            }
        }
        
        System.out.println(remainingTrees);
    }
}

import sys

def solve():
    l, m = map(int, sys.stdin.readline().split())
    
    # 差分数组
    diff = [0] * (l + 2)
    
    for _ in range(m):
        u, v = map(int, sys.stdin.readline().split())
        diff[u] += 1
        diff[v + 1] -= 1
        
    remaining_trees = 0
    coverage = 0
    
    # 计算前缀和并统计
    for i in range(l + 1):
        coverage += diff[i]
        if coverage == 0:
            remaining_trees += 1
            
    print(remaining_trees)

solve()

算法及复杂度

  • 方法一：标记法
    • 算法: 数组模拟/标记法。
    • 时间复杂度: 。最坏情况下，每个区域都覆盖整个马路，复杂度接近 。L 来自于最后的统计（或初始化），M*L来自于 M 个区域的标记过程。鉴于本题 L 和 M 的范围，这个复杂度是完全可以接受的。
    • 空间复杂度: ，用于创建模拟马路的数组。
  • 方法二：差分数组
    • 算法: 差分数组。
    • 时间复杂度: 。O(M) 用于遍历 M 个区间并更新差分数组，O(L) 用于计算前缀和并统计结果。
    • 空间复杂度: ，用于创建差分数组。