光头强喊你砍树啦

题目描述

某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是 1 米。我们可以把马路看成一个数轴，马路的一端在数轴 00的位置，另一端在 L 的位置；数轴上的每个整数点，即 0，1，2，⋯，L，都种有一棵树。

由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。

输入格式

第一行有两个整数：L（ 1≤L≤10000 ）和 M（ 1≤M≤100 ），LL 代表马路的长度，MM 代表区域的数目，LL 和 MM 之间用一个空格隔开。接下来的 MM 行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。

输出格式

包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。

样例输入

500 3
150 300
100 200
470 471

样例输出

298

AC代码

#include <stdio.h>
int main()
{
    int L,M;
    scanf("%d %d",&L,&M);
    int a[101][2];//用于存储区域的左右端点
    for(int i=0;i<M;++i)
        scanf("%d %d",&a[i][0],&a[i][1]);

    //原来共L棵树
    int cuted[10001]={0};//初始化为0，代表未被砍去
    int cut1=a[0][1]-a[0][0]+1;//事先处理好第一个区域
    for(int i=a[0][0];i<=a[0][1];++i)
    {
        cuted[i]=1;//1代表已被砍去
    }
    //printf("cut1=%d\n",cut1);
    int len=L+1;//加1是因为数轴0处也有一棵树
    len-=cut1;
    int cnt;
    for(int i=1;i<M;++i)
    {

        cnt=0;//此次实际应该砍去的树的个数
        for(int j=a[i][0];j<=a[i][1];++j)
        {
            if(cuted[j]==0)//还未曾被砍去
            {
                ++cnt;
                cuted[j]=1;//mmp!!!!!!
            }
        }
        //printf("cnt=%d\n",cnt);
        len-=cnt;
    }
    printf("%d",len);
}

后记

17分钟搞定，然后测试–>出错

调试中….

a thousand years lator…

卧槽！忘了把后来那些被砍位置置1

仅仅少写了一行代码cuted[j]=1;

却花费了很久才找到

果然是–

上联：编程3分钟

下联：调试3小时

横批：头发！

~~~

20200517更新

直接开一个辅助数组，初始全1，代表有树，砍去则置0，最后输出为1的个数即可