JiaDu_Yin @ 2023-11-24 16:51:30
#include <stdio.h>
#include <stdlib.h>
int f(int a,int b,int c,int d)
{
if(c>b||a>d) return 0;
if(b>c&&b<d&&a<c) return b-c+1;
if(d>a&&d<b&&c<a) return d-a+1;
if(a<=c&&b>=d) return d-c+1;
if(c<a&&d>b) return b-a+1;
}
int main()
{
int l,t; //l表示总长,t表示区域数
scanf("%d%d",&l,&t);
int u[t],v[t],x[t];
int num=l+1;//表示剩余的树的数量;
for(int n=0;n<t;n++)
{
scanf("%d%d",&u[n],&v[n]);
x[n]=v[n]-u[n]+1; //表示区域内的树的数量;
num-=x[n];
}
//两个区域一组,检测重合部分
for(int i=0;i<t-1;i++)
for(int j=i+1;j<t;j++)
num+=f(u[i],v[i],u[j],v[j]);
if(num<0) num=0;
printf("%d",num);
}
by Bingxiu @ 2023-11-24 17:34:08
@JiaDu_Yin 三个区间有交集,如
by JiaDu_Yin @ 2023-11-24 19:45:47
@Bingxiu 对哦,谢谢,那看来这个思路不太好,本来觉得这样时间复杂度小