校门外的树

时间: 1ms        内存:128M

描述:

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

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

输入:

输入的第一行有两个整数L1 <= L <= 10000)和 M1 <= M <= 100),L代表马路的长度,M代表区域的数目,LM之间用一个空格隔开。接下来的M行每行包含两个不同的整数,用一个空格隔开,表示一个区域的起始点和终止点的坐标。

输出:

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

示例输入:

500 3
150 300
100 200
470 471

示例输出:

298

提示:

参考答案(内存最优[1120]):

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int L,M;
    scanf("%d%d",&L,&M);
    int shu[10000]={0},i;
    int tq,tj,j,s=0;
    for(i=0;i<M;i++)
    {
        scanf("%d%d",&tq,&tj);
        for(j=tq-1;j<tj;j++)
            shu[j]=1;
    }
    for(i=0;i<L;i++)
        if(shu[i]==0)
            s++;
    printf("%d",s+1);
}

参考答案(时间最优[2]):

#include<stdio.h>

int a[10001];

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int i,j,l,r,s=n+1;
    for(i=0;i<=n;++i) a[i]=1;
    for(i=1;i<=m;++i)
    {
        scanf("%d%d",&l,&r);
        for(j=l;j<=r;++j)
        {
            if(a[j]) s--;
            a[j]=0;
        }
    }
    printf("%d",s);
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。