文章目录
- 问题描述
- 输入格式
- 输出格式
- 输出要求
- 输入样例
- 输出样例
- 解题思路
- 图示
- Java代码
- C代码
- C++代码
- Java代码输出结果
问题描述
某校大门外长度为 L的马路上有一排树，每两棵相邻的树之间的间隔都是 1米。我们可以把马路看成一个数轴，马路的一端在数轴 0 的位置，另一端在 L 的位置；数轴上的每个整数点，即 0,1,2,…,L，都种有一棵树。
由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。
输入格式
第一行有两个整数，分别表示马路的长度 L和区域的数目 m。
接下来 m 行，每行两个整数 u,v，表示一个区域的起始点和终止点的坐标。
输出格式
输出一行一个整数，表示将这些树都移走后，马路上剩余的树木数量。
输出要求
输出包括一行，这一行只包含一个整数，表示马路上剩余树的数目。
输入样例
500 3
150 300
100 200
470 471
输出样例
298
解题思路
我们先把题目的意思搞明白，这里可以用 “模拟法” 来解决问题，而其基本思想是对事物进行抽象，将现实世界的事物映射成计算机所能识别的代码符号。具体的问题具体分析，这里是 “校门外的树” ，那么我们把这个题目描述的现实具体的“移树”问题进行抽象，变成数学符号以及代码符号来理解。
现实世界 ->抽象世界
- 数学思想
在一个数轴上，对指定区间 [0,L] 上的整数点进行取值，假设数轴上所有点的权为0 或 false，现给出几个 已知的 [u,v]小区间，要求把这几个小区间中的整数点（包括两个端点）的权更改为 1 或 true。最后统计数轴 [0,L] 上还有几个 权等于0 的点的个数，记为 num。 求出num的值。
NOTE ： 这里为什么选择赋值的方式来进行对树移或者未移进行标记？ 因为现实生活中，我们给出的几个区间是会出现交集的部分，但是我们却不能把移走的树的位置再进行移动一遍，所以我们只需要把已经移走的树的位置进行标记，这个标记肯定选择一个相同的值最好，因为最后我们使用if语句数留下来的树的数目的时候只用写一个判断条件，就可以直接判断出树的状态。
- 编程思想
使用模拟法对题目进行抽象，通过在数轴上进行取值的方式进行标记，最后统计剩余树的个数。
-
数据结构的选择
可以考虑使用一个数组或列表来表示数轴上的点。
-
标记的方式
如果将区间内的整数点的权更改为1，可以考虑使用布尔类型的数组或列表，这样可以更节省空间。而不是用0和1表示，可以用
True和False。 -
区间的处理
在处理区间时，可以考虑使用一个循环，遍历所有区间，将区间内的点进行标记，而不是逐一处理每个区间。
我简单列举一个例子，然后把示意图画出来。
输入描述 ：11 3 2 5 4 59 10输出描述 ：6
图示
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();}
}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;
}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;
}
Java代码输出结果
例题代码测试结果
原题目代码测试结果
三连支持一下，感谢！
