【代码+图解+解析】校门外的树

问题描述

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

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

输入格式

第一行有两个整数，分别表示马路的长度 L和区域的数目 m。

接下来 m 行，每行两个整数 u,v，表示一个区域的起始点和终止点的坐标。

输出格式

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

输出要求

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

输入样例

500  3
150  300
100  200
470  471
1
2
3
4

输出样例

298
1

解题思路

我们先把题目的意思搞明白，这里可以用 “模拟法” 来解决问题，而其基本思想是对事物进行抽象，将现实世界的事物映射成计算机所能识别的代码符号。具体的问题具体分析，这里是 “校门外的树” ，那么我们把这个题目描述的现实具体的“移树”问题进行抽象，变成数学符号以及代码符号来理解。

现实世界 ->抽象世界

• 数学思想

在一个数轴上，对指定区间 [0,L] 上的整数点进行取值，假设数轴上所有点的权为0 或 false，现给出几个 已知的 [u,v]小区间，要求把这几个小区间中的整数点（包括两个端点）的权更改为 1 或 true。最后统计数轴 [0,L] 上还有几个 权等于0 的点的个数，记为 num。 求出num的值。

NOTE ： 这里为什么选择赋值的方式来进行对树移或者未移进行标记？ 因为现实生活中，我们给出的几个区间是会出现交集的部分，但是我们却不能把移走的树的位置再进行移动一遍，所以我们只需要把已经移走的树的位置进行标记，这个标记肯定选择一个相同的值最好，因为最后我们使用if语句数留下来的树的数目的时候只用写一个判断条件，就可以直接判断出树的状态。

• 编程思想

使用模拟法对题目进行抽象，通过在数轴上进行取值的方式进行标记，最后统计剩余树的个数。

1. 数据结构的选择

   可以考虑使用一个数组或列表来表示数轴上的点。

2. 标记的方式

   如果将区间内的整数点的权更改为1，可以考虑使用布尔类型的数组或列表，这样可以更节省空间。而不是用0和1表示，可以用True和False。

3. 区间的处理

   在处理区间时，可以考虑使用一个循环，遍历所有区间，将区间内的点进行标记，而不是逐一处理每个区间。

---

我简单列举一个例子，然后把示意图画出来。

输入描述 ：
     11    3    
     2     5    
     4     5
     9    10
     
输出描述  ：
      6
1
2
3
4
5
6
7
8

图示

---

Java代码

import java.util.Scanner;

public class RemainingTrees {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取输入
        int L = scanner.nextInt();
        int m = scanner.nextInt();
        int[] treeStatus = new int[L + 1]; 
        // 标记移走的树的位置
        for (int i = 0; i < m; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            for (int j = u; j <= v; j++) {
                treeStatus[j] = 1;
            }
        }
        // 统计剩余树的数量
        int remainingTreesCount = 0;
        for (int i = 0; i <= L; i++) {
            if (treeStatus[i] == 0) {
                remainingTreesCount++;
            }
        }
        // 输出结果
        System.out.println(remainingTreesCount);

        scanner.close();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

---

C代码

#include <stdio.h>

int main() {
    int L, m;
    scanf("%d %d", &L, &m);

    int treeStatus[L + 1];  // 数轴上的树的状态，0表示未移走，1表示已移走
    for (int i = 0; i <= L; i++) {
        treeStatus[i] = 0;
    }
    // 标记移走的树的位置
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        for (int j = u; j <= v; j++) {
            treeStatus[j] = 1;
        }
    }
    // 统计剩余树的数量
    int remainingTreesCount = 0;
    for (int i = 0; i <= L; i++) {
        if (treeStatus[i] == 0) {
            remainingTreesCount++;
        }
    }
    // 输出结果
    printf("%d\n", remainingTreesCount);

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

---

C++代码

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int L, m;
    cin >> L >> m;

    vector<int> treeStatus(L + 1, 0);  // 数轴上的树的状态，0表示未移走，1表示已移走
     // 标记移走的树的位置
        int u, v;
    for (int i = 0; i < m; i++) {   
        cin >> u >> v;
        for (int j = u; j <= v; j++) {
            treeStatus[j] = 1;
        }
    }
    // 统计剩余树的数量
    int remainingTreesCount = 0;
    for (int i = 0; i <= L; i++) {
        if (treeStatus[i] == 0) {
            remainingTreesCount++;
        }
    }
    // 输出结果
    cout << remainingTreesCount << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

---

Java代码输出结果

例题代码测试结果

原题目代码测试结果

---

三连支持一下，感谢！