NOIP 380. 校门外的树
| 发布于 | 2020-03-12 17:24 |
题干
某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。
由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。
输入
第一行有两个整数L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。
接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。
500 3
150 300
100 200
470 471输出
输出包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。
298来源
NOIP 2005年普及组第二题，收录于NOIPOJ第380题。
解题思路
题目第一句非常具有迷惑性，极其容易让人联想到数组长度就是L，实际上这里的长度指数轴上的长度，即0到L的距离，但在求解过程中，将0到L存入数组，总计存入L+1个数（数组长度）。
0到1的距离为1，0到1有2个数；
0到2的距离为2，0到2有3个数；
0到100的距离为100，0到100有101个数；
……
0到L的距离为L，0到L有L+1个数。我的解法是将所有区间抽象为起点和终点，并叠加到一条线段上。
我将某一个起点记为+1，某一个终点记为-1，其余位置记为0，并使用一维数组trees来存储这条线段（即存储区间起点和终点的的叠加值）。
若两个起点位置相同，则叠加得到+2；若两个终点位置相同，则叠加得到-2；若某一个起点和某一个终点位置相同（两个区间合并为一个区间），则叠加得到0。
存储完所有区间后，遍历这条线段上的叠加结果，在遍历时将每个叠加结果依次累加到变量stack中。
因为起点和终点必然成对存在，即+1和-1的个数必定相等，那么当没有进入或已经离开所有区间的时候，stack必定为0，而只要遍历位置在任意一个区间时，累加的stack必定大于0（按我定义的正负来说）。
package top.qlin.leo;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sr = new Scanner(System.in);
/** 马路上的树（没有移走之前），总共有L+1棵。 */
byte[] trees = new byte[sr.nextInt() + 1];
/** 区域个数。用于确定循环次数。 */
int time = sr.nextInt();
// 循环time次，读取所有“区域”。
// 如果某区域的终点和另一个区域的起点重叠，这种方法可以自动合并两个区域。
for (int t = 0; t < time; t++) {
trees[sr.nextInt()]++; // 这里输入的int是该区域的起点位置。
trees[sr.nextInt()]--; // 这里输入的int是区域的终点位置。
}
sr.close();
/** 某一位置的“树”身处的区域的个数。 */
int stack = 0,
/** 当前未被移走的树的数量 */
quantity = 0;
// 遍历trees以统计剩余树的数量。
for (int i = 0; i < trees.length; i++) {
// stack != 0表示第i棵树身处stack个叠加的区域中。
// trees[i] != 0表示第i棵树不在区域的两个端点上。
if (trees[i] != 0 || stack != 0) {
stack += trees[i];
} else {
quantity++;
}
}
System.out.print(quantity);
}
}