记录下算法入门课提到的几种方法

方法一，暴力

开长度为L的数组，记录下拔掉多少少树然后减掉就可以了，最差的情况是t == m && x == 0 && y == l，时间复杂度是O(m*l)。

    int l = 0,t = 0,L[10005]={0};
    scanf("%d %d",&l,&t);
    memset(L,0,sizeof(L));
    int sum = 0;
    int x,y;
    while(t-->0)
    {
        scanf("%d %d",&x,&y);
        for(int i = x;i<=y;i++)
        {
            if(!L[i])
            {
                L[i] = 1;
                sum++;
            }
        }
    }
    printf("%d",l-sum+1);

方法二，差分

对拔起的起点加一，末尾后一个减一，循环m次。

从起点遍历到终点，当a == 0时，意为没被拔，树的数量加一。

时间复杂度是O(m+l);

还可以用于计算这个地方被拔了几次（乐）。

    int l = 0,m = 0;
    int delta[10005] = {0};
    memset(delta,0,sizeof(delta));
    int sum = 0,a =0;
    int x,y;
    scanf("%d %d",&l,&m);
    for(int i = 0;i<m;i++)
    {
        scanf("%d %d",&x,&y);
        if(x>y)
        {
            a = x;
            x = y;
            y = a;
        }
        delta[x]++;
        delta[y+1]--;
    }
    a = 0;
    for(int i = 0;i<=l;i++)
    {
        a+=delta[i];
        if(a == 0) sum++;
    }
    printf("%d",sum);

方法三，合并区块后直接减掉区块长度

时间复杂度O(2*m)

struct cl
{
    int l;
    int r;
}cl[1005];
bool cmp(struct cl x,struct cl y) 
{
    return x.l < y.l?1:0;
}
int main()
{
    int l = 0,m = 0;
    scanf("%d %d",&l,&m);
    for(int i = 0;i<m;i++)
    {
        scanf("%d %d",&cl[i].l,&cl[i].r);
    }
    sort(cl,cl+m,cmp);//讲区间按左边界排序
    int cnt = l+1,le = cl[0].l, ri = cl[0].r;//记录上一个（最大）区块
    for(int i = 1;i<m;i++)
    {
        if(cl[i].l<ri) ri = ri>cl[i].r?ri:cl[i].r;//如果右边界在上一个区块，则保留最左的左边界
        else//当右边界不在上一个区块中间，则将总长减去刚刚的区块（最大），然后更新左右边界
        {
            cnt-=(ri-le+1);
            ri = cl[i].r;
            le = cl[i].l;
        }
    }
    cnt-=(ri-le+1);//最后再减一次
    printf("%d",cnt);
    return 0;
}

方法四，离散化

是离散的差分，时间复杂度O(3*m)，略高，开的数组也更大，但是相比前面的差分还是效率高不少，做扩展用在，终点是把这个差分做的与数轴无关

struct cl
{
    int w;
    int n;
}cl[2005];
bool cmp(struct cl x,struct cl y) 
{
    if(x.w == y.w) return x.n < y.n;
    else return x.w < y.w;
}
int main()
{
    int l = 0,m = 0;
    scanf("%d %d",&l,&m);
    for(int i = 0;i<m;i++)
    {
        scanf("%d %d",&cl[i].w,&cl[i+m].w);
        cl[i].n = +1;
        cl[i+m].n = -1;
        cl[i+m].w;
    }
    sort(cl,cl+2*m,cmp);
    int cnt = cl[0].w,a = 1,le = 0,ri = 0;
    for(int i = 1;i<2*m;i++)
    {
        a += cl[i].n;
        if(a == 1 && cl[i].n == 1 ) cnt+=(cl[i].w - cl[i-1].w - 1);
    }
    cnt+=l - cl[2*m-1].w;
    printf("%d",cnt);
    return 0;
}