AcWing 422. 校门外的树(差分)
原题链接
简单
作者:
𝓒𝓸𝓬𝓪𝓒𝓸𝓵𝓪_8
,
2021-01-16 19:34:34
,
所有人可见
,
阅读 288
差分
使用差分来操作
首先将所有的点的值都设置为0
如果某一个区间要移树,那么就将这个区间中的所有点的值都加上1
那么如果这个点的值为0,说明还有树,如果不为0,那么就说明没树
最后遍历一遍,有树+1,没树不加就可以了
时间复杂度(L + M)
C++ 代码
#include <bits/stdc++.h>
using namespace std ;
int f[10005] ; //最开始所有点的值为0,差分也为0
int main(){
int L , m ;
cin >> L >> m ;
while(m --){
int l , r ;
cin >> l >> r ;
f[l] ++ ;
f[r + 1] -- ; //将这个区间的每一个点+1
}
int ans = 0 , s = 0 ; //初始值为0
for (int i = 0 ; i <= L ; ++ i){
s += f[i] ; //初始值加上差分等于当前这个点的值
ans += !s ; //如果为0那么+1,反之+0
}
cout << ans ; //输出结果
return 0 ;
}