首页 > 试题广场 >

剩下的树

[编程题]剩下的树

热度指数：30170 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

有一个长度为整数L(1<=L<=10000)的马路，可以想象成数轴上长度为L的一个线段，起点是坐标原点，在每个整数坐标点有一棵树，即在0,1,2，...，L共L+1个位置上有L+1棵树。现在要移走一些树，移走的树的区间用一对数字表示，如 100 200表示移走从100到200之间（包括端点）所有的树。可能有M(1<=M<=100)个区间，区间之间可能有重叠。现在要求移走所有区间的树之后剩下的树的个数。

输入描述:

    两个整数L(1<=L<=10000)和M(1<=M<=100)。
    接下来有M组整数，每组有一对数字。

输出描述:

    可能有多组输入数据，对于每组输入数据，输出一个数，表示移走所有区间的树之后剩下的树的个数。

示例1

输入

输出

算法知识视频讲解

三叶不晚

#include<stdio.h>
int tree[10000]={0};
int main(){
    int length;
    int zushu;
    int i;
    int j;
    int low;
    int high;
    int sum=0;
    while(scanf("%d%d",&length,&zushu)!=EOF){

for(i=0;i<zushu;i++){
    scanf("%d%d",&low,&high);
for(j=low;j<=high;j++){
    if(tree[j]==0){
        continue;
            }
            else{
                tree[j]=1;
            }
        }
    }
for(i=0;i<=length;i++)
if(tree[i]==0)
sum++;
printf("%d\n",sum);
    }
return 0;

}

发表于 2022-03-20 11:44:16 回复(0)

李顺利plus

超级暴力求解

#include<stdio.h>
struct tree
{
    int a;
    int b;
};
int main()
{
    int L,M,sum=0;
    scanf("%d",&L);
    scanf("%d",&M);
    struct tree kanshu[M];
    int shu[L+1];
    for(int i=0;i<=L;i++)
    {
        shu[i]=1;
    }
    for(int i=0;i<M;i++)
    {
        scanf("%d",&kanshu[i].a);
        scanf("%d",&kanshu[i].b);
        for(int j=kanshu[i].a;j<=kanshu[i].b;j++)
        {
            shu[j]=0;
        }
    }
    for(int i=0;i<=L;i++)
    {
        if(shu[i]==1)
        {
            sum++;
        }
    }
    printf("%d",sum);
    return 0;
}

发表于 2022-03-07 21:03:36 回复(0)