课程29_13 1110 校门外的树

---

题目：

题目描述:

某校大门外长度为 L 的马路上有一排树，每两棵相邻的树之间的间隔都是 1 米。我们可以把马路看成一个数轴，马路的一端在数轴 0 的位置，另一端在 L 的位置；数轴上的每个整数点，即 0, 1, 2, …, L，都种有一棵树。由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。

输入描述：

输入两个整数 L (1 <= L <= 100000) 和 M (1 <= M <= 100)，L 代表马路的长度，M 代表区域的数目，L 和 M 之间用一个空格隔开。接下来的 M 行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。

输出描述：

占一行，马路上剩余的树的数目

样例输入:

500 3
150 300
100 200
470 471

样例输出:

298

---

解析：

这道题其实没什么花里胡哨的，模拟法就可以过，也就是开一个100000长度的数组，然后按照输入去变化数组里的值，最后计算一共还有多少棵树剩下来。

但是其实这样做有些危险，如果数据再大一些，很有可能执行效率不够。因为很明显，每拔一棵树，就会操作一次数组，但是我们不需要知道哪些树被拔了，因为拔掉的树 = 开始拔的位置-结束拔的位置+1（因为开头和结尾都被拔了 所以要加一）。这种方法的关键难点就在于：拔树的区间可能是重叠的，比如150~300与100~200就有一定的重叠，他们的真实区间其实是100~300。

我的解决方法是“括号法”，什么意思呢。首先我们把每个区间的左右端点写下来，如果是左端点，就加一个左括号，如果是右端点，就加一个右括号，那么题目给出的数据是这样的：

(150 300) (100 200) (470 471)

然后我们按照数字给他们排序，记得括号也要跟着移动：

(100 (150 200) 300) (470 471)

随后我们只看最外层的括号，在括号里面的数据全部删掉。比如“(150”和“200)”就在括号里，就要删掉。

(100 300) (470 471)

那么这样就留下了不重叠的区间了。

如何判断数据是否在括号里呢？答案很简单，开一个变量，如果碰到一个左括号，就+1，如果碰到一个右括号，就-1。那么这个变量大于等于1的时候，碰到的数据就是在括号里的，反之就不在括号里。

---

解题：

这里代码给出的是比较简单的模拟法，题目中提到的优化方法代码就不给出了，大家可以自己思考完成。（建议使用结构体或者类 去管理“节点”，因为每个节点除了要存储数字以外，还要存储它是左节点还是右节点）

参考代码：

// TSOJ-1110 校门外的树
#include <iostream>
using namespace std;

int main()
{
	int L,M,left,right,count;
	while(cin>>L>>M)
	{
		bool tree[L+1];
		for(int i=0;i<=L;i++)
			tree[i] = true;
		for(;M--;){
			cin>>left>>right;
			for(int i=left;i<=right;i++)
				tree[i] = false;
		}
		count = 0;
		for(int i=0;i<=L;i++)
			if(tree[i])
				count++;
		cout<<count<<endl;
	}
	return 0;
}