校门外的树

本是古典何须时尚 2022-11-25 13:25 128阅读 0赞

某校大门外长度为 l的马路上有一排树，每两棵相邻的树之间的间隔都是 1 米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在 l 的位置；数轴上的每个整数点，即 0,1,2,…,l都种有一棵树。  
由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。

###### 输入格式 ######

第一行有两个整数，分别表示马路的长度 lll 和区域的数目 m。  
接下来 m 行，每行两个整数 u,v，表示一个区域的起始点和终止点的坐标。

###### 输出格式 ######

输出一行一个整数，表示将这些树都移走后，马路上剩余的树木数量。

###### 输入 ######

500 3  
150 300  
100 200  
470 471

##### 输出 #####

298

###### 说明/提示 ######

###### 数据规模与约定 ######

对于 20%的数据，保证区域之间没有重合的部分。  
对于 100%的数据，保证 1≤l≤104，1≤m≤100，0≤u≤v≤l。

//使用标记方法简化问题
    #include <iostream>
    #include<string.h>
    using namespace std;
    int main()
    { 
        int l,m,cnt=0;
        cin>>l>>m;
        int a[l+1];
        memset(a,0,sizeof(a));
        for(int i=0;i<m;i++)
        { 
      	int h,t=0;
      	cin>>h>>t;
      	for(int j=h;j<=t;j++)
      	{ 
               if(a[j]==0)
       	   { 
                  a[j]=1;
        	   } 
            } 
        }
        for(int k=0;k<=l;k++)
        { 
      	if(a[k]==0)
      	{ 
                cnt++;
      	}
        } 
        cout<<cnt<<endl;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，128人围观）

还没有评论，来说两句吧...

相关阅读

相关校门外的树

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

本是古典何须时尚/ 2022年11月25日 13:25/ 0 赞/ 129 阅读

相关 Sicily 1145 校门外的树

思路：初始化数组num，对于每一个区域，分别进行标记，即是使其对应的num值为1，最后求出num中值为0的个数。代码： \include<iostream>

Love The Way You Lie/ 2022年08月06日 12:22/ 0 赞/ 127 阅读

相关校门外的树 UESTC - 62

校门外的树 UESTC - 62 -------------------- Problem 某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是11米

ゞ浴缸里的玫瑰/ 2022年06月14日 10:41/ 0 赞/ 133 阅读

相关 1154: 校门外的树

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

﹏ヽ暗。殇╰゛Y/ 2022年06月11日 03:50/ 0 赞/ 163 阅读

相关蓝桥杯 - 校门外的树

用数组的方法把，每一棵树的状态标记，然后根据输入操作标记即可。 include<iostream> include<cstdio> include<c

我就是我/ 2022年06月01日 02:29/ 0 赞/ 206 阅读

相关 ALGO-29 算法训练校门外的树

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

秒速五厘米/ 2022年05月26日 10:13/ 0 赞/ 139 阅读

相关 NOIP 2005 校门外的树

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

落日映苍穹つ/ 2022年05月16日 01:05/ 0 赞/ 246 阅读

相关 VIJOS 校门外的树

[题目传送门][Link 1] 每个询问其实是求前面有多少个区间与之相交答案就是：前面区间数量-与前面区间不相交数量与前面区间不相交数量=前面区间 l 大于询问

痛定思痛。/ 2022年05月11日 01:34/ 0 赞/ 149 阅读

相关 XOJ 1569：校门外的树

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

本是古典何须时尚/ 2022年02月13日 10:59/ 0 赞/ 173 阅读

相关校门外的树1110

题目描述: > 某校大门外长度为 L 的马路上有一排树，每两棵相邻的树之间的间隔都是 1 米。我们可以把马路看成一个数轴，马路的一端在数轴 0 的位置，另一端在 L 的位

太过爱你忘了你带给我的痛/ 2021年11月02日 01:54/ 0 赞/ 282 阅读