1099: 校门外的树

解题思路:

暴力解法，建一个大小为n的数组存储树的状态。时间复杂度是O(n)，题解里面那个扫描线差分我还没看懂。

注意事项:

太暴力太丑陋了。

参考代码:

// 题目 1099: 校门外的树
#include using namespace std;

int main(){
	int len = 0; // 街道长度
	int num = 0; // 区域数目
	cin >> len >> num;
	
	bool street[len] = { 0 }; // 标记，0表示还在，1表示被拔
	while (num--){
		int start = 0; // 每次拔树的起始点
		int end = 0; // 每次拔树的终止点
		cin >> start >> end;
		for(int i = start; i <= end; i++){
			street[i] = 1; // 被拔就改成1
		}
	}
	
	int res = 0; // 剩余树数
	for(int i = 0; i <= len; i++){
		if(!street[i]){
			res++;
		}
	}
	cout << res << endl;
	return 0;
}