校门外的树
题目来源：《NOIP2005普及组》
时间限制：1000ms 内存限制：128mb
题目描述
某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。
我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。
由于马路上有一些区域要用来建地铁。
这些区域用它们在数轴上的起始点和终止点表示。
已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。
现在要把这些区域中的树（包括区域端点处的两棵树）移走。
你的任务是计算将这些树都移走后，马路上还有多少棵树。
输入格式
输入文件的第一行有两个整数L和M，L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。
接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。
输出格式
输出文件包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。
数据范围
(1≤L≤10000),
(1≤M≤100)
样例输入
500 3
150 300
100 200
470 471
样例输出
298
解题思路1：暴力破解（模拟）
1.声明一个(boolean)数组(tree[])表示马路，长度为(L+1)，其中的每个元素代表树的状态:(begin{cases}true: 有树 \false：没有树end{cases})
2.遍历给定的每一个区域，将区域内的树移走，即：(tree[i] = false)
3.统计移走所有给定区域的树之后剩余的树，即：(tree)数组内有多少值为(true)的项。
解题代码1-Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int l = input.nextInt();
int m = input.nextInt();
boolean[] tree = new boolean[l + 1];
for (int i = 0; i <= l; i++) {
tree[i] = true;
}
for (int i = 0; i < m; i++) {
int start = input.nextInt();
int end = input.nextInt();
for (int j = start; j <= end; j++) {
tree[j] = false;
}
}
input.close();
int res = 0;
for (int i = 0; i <= l; i++) {
res += (tree[i] ? 1 : 0);
}
System.out.println(res);
}
}
解题思路2：区间合并
1.将要砍掉树的区间合并在一起，合并后的区间没有重合部分。例如：[1-3]和[3-5] 合并成 [1-5]。
2.树的总数 - 合并后所有区间覆盖的点数 = 剩余树的数量。
区间合并：
1.将区间按左端点升序排序。
2.从第一个区间开始，如果该区间的右端点大于后面相邻区间的左端点，当前区间右端点更新为：该区间右端点和相邻区间右端点最大值。直到不能继续合并，然后开始后面区间合并。
解题代码2-Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int l = input.nextInt();
int m = input.nextInt();
int[][] road = new int[m][2];
for (int i = 0; i < m; i++) {
road[i][0] = input.nextInt();
road[i][1] = input.nextInt();
}
input.close();
Arrays.sort(road, new Comparator<int[]>() { //按照二维数组的首项排序，首项相同按第二项排序
@Override
public int compare(int[] o1, int[] o2) {
if (o1[0] == o2[0])
return o1[1] - o2[1];
return o1[0] - o2[0];
}
});
int res = l + 1;
int start = road[0][0], end = road[0][1];
for (int i = 1; i < m; i++) {
if (end >= road[i][0]) {
end = Math.max(end, road[i][1]);
} else {
res -= end - start + 1;
start = road[i][0];
end = road[i][1];
}
}
res -= end - start + 1;
System.out.println(res);
}
}
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
