题目描述
我们需要将需要移除的部分移除,然后计算剩下的树木还有多少棵
思路分析:
1)使用标记法,将所有的树木首先设置为true
2)将区间内的树木设置为flase,当然需要判断首先这颗树木是否在之前被移除了
细节:
1)数轴的零点也是有树木的,否则样例计算出来少1
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
C++ 代码
#include <iostream>
using namespace std;
int L,M;
int ans;
int tree[10010];
int main(){
cin >> L >> M;
for(int i = 0; i <= L; i++){
tree[i] = true;
}
for(int i = 1; i<=M ; i++){
int l , r;
cin >> l >> r;
for(int j = l;j<=r;j++){
if(tree[j]) tree[j] = false;
}
}
for(int i = 0;i<=L;i++){
if(tree[i]) ans++;
}
cout << ans;
return 0;
}