校门外的树

方法一

首先建立一个数组,将其初值全部设置为1表示在该位置上有树。然后输入多组区间,将其区间内的数组值修改为0表示树被移走。最后遍历数组,若数组值为1则表示树还在。本题要注意的是边界问题：int i = 0;i <= l;i++ 闭区间【0,l】

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int N  = 10010;
int tree[N];
int l,m;
int cnt;

int main()
{
    scanf("%d%d",&l,&m);
    //数组值为1表示有树
    for (int i = 0;i <= l;i++) tree[i] = 1; 
    while (m--)
    {
        int x1,x2;
        scanf("%d%d",&x1,&x2);
        //数组值为0表示树被移走
        for (int j = x1;j <= x2;j++) tree[j] = 0;
    }
    for (int i = 0;i <= l;i++)
            if (tree[i] == 1)
                cnt += 1;
    printf("%d\n",cnt);
    return 0;
}

方法二：差分

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010;
int delta[N];//差分数组
int tree[N];
int l,m;
int cnt;

int main()
{
    scanf("%d%d",&l,&m);
    //tree数组值为1表示当前位置有树,该语句可以省略
    for (int i = 0;i <= l;i++) tree[i] = 1;
    //由于tree数组全为1，所以差分数组只有第0位为1,其余位置全为0
    delta[0] = 1;
    while (m--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        //修改差分数组
        delta[x]--;
        delta[y + 1]++;
    }

    //位置0需要单独特判
    if (delta[0] > 0) cnt += 1;
    //对差分数组求和得原数组
    for (int i = 1;i <= l;i++)
    {
        delta[i] += delta[i - 1];
        if (delta[i] > 0) cnt += 1;
    }
    printf("%d",cnt);
    return 0;
}