提问,模拟人手运算,不知道哪些情况没有考虑到

P1047 [NOIP2005 普及组] 校门外的树

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 三个区间有交集,如 [1,4],[2,5],[3,6]


by JiaDu_Yin @ 2023-11-24 19:45:47

@Bingxiu 对哦,谢谢,那看来这个思路不太好,本来觉得这样时间复杂度小


|