题目大意:有一段长度为L的路上每个整数点都种满着树(0点也有树),然后给定M个区间,该区间内的树会被砍掉,并各个区间有可能重叠,输出最后剩余的树的数量
思路:上了雨巨的课想法就是差分啦(虽然有看一眼代码,思路就是把给定区间的端点值进行修改,要计算有多少树存活时再利用端点值进行计算
代码如下:
#include
using namespace std;
int main()
{
int L,t;
int a[100000]= {0};
cin>>L>>t;
while(t--)
{
int b,c;
cin>>b>>c;
a[b]--;
a[c+1]++;
}
int ok=0,cnt=0;
if(a[0]>=0)cnt++;
for(int i=1; i<=L; i++)
{
a[i]+=a[i-1];
if(a[i]>=0)
{
cnt++;
}
}
cout<<cnt;
return 0;
}