`
- 浏览:
840137 次
-
问题描述
某校大门外长度为 L 的马路上有一排树,每两棵相邻的树之间的间隔都是1 米。我们
可以把马路看成一个数轴,马路的一端在数轴0 的位置,另一端在L 的位置;数轴上的每
个整数点,即0,1,2,……,L,都种有一棵树。
由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已
知任一区域的起始点和终止点的坐标都是整数,区域之间可能有重合的部分。现在要把这些
区域中的树(包括区域端点处的两棵树)移走。你的任务是计算将这些树都移走后,马路上
还有多少棵树。
输入数据
输入的第一行有两个整数L(1 <= L <= 10000)和 M(1 <= M <= 100),L 代表马路
的长度,M 代表区域的数目,L 和M 之间用一个空格隔开。接下来的M 行每行包含两个不
同的整数,用一个空格隔开,表示一个区域的起始点和终止点的坐标。
输出要求
输出包括一行,这一行只包含一个整数,表示马路上剩余的树的数目。
输入样例
500 3
150 300
100 200
470 471
输出样例
298
解题思路
这个问题可以概括为输入一个大的整数闭区间,及一些可能互相重叠的在该大区间内的
小的整数闭区间。在大的整数闭区间内去除这些小的整数闭区间,问之后剩下的可能不连续
的整数区间内有多少个整数。这个题目给出的范围是大的区间在1~10000 以内,要去除的小
的区间的个数是100 个以内。因为规模较小,所以可以考虑用空间换时间,用一个大数组来
模拟这些区间,数组中的每个数表示区间上的一个数。例如,如果输入L 的长度是500,则
据题意可知最初有501 棵树。我们就用一个501 个元素的数组来模拟这501 棵树,数组的下
标分别代表从1 到501 棵树,数组元素的值代表这棵树是否被一走。最初这些树都没有被移
走,所以所有数组元素的值都用true 来表示。每当输入一个小区间,就将这个区间对应的
树全部移走,即将这个区间对应的数组元素下标指示的元素的值置成false。如果有多个区
间对应同一个数组元素,会导致多次将某个数组元素置成false。不过这并不影响结果的正
确性。当所有小区间输入完成,我们可以数一下剩下的仍旧为true 的元素的个数,就可以
得到最后剩下的树的数目。当然如果最开始输入的区间不是500,则我们使用的数组大小就
不是500。因为题目给出的上限是10000,所以我们可以定义一个大小是10001 个元素的数
组,这样对所有输入都是够用的。
参考程序:
分享到:
Global site tag (gtag.js) - Google Analytics
相关推荐
高中地理 2.3季风例题 湘教版必修1
高中地理 2.3三圈环流和移动例题 湘教版必修1
高中地理 2.3大气热力环流和风例题 湘教版必修1
图像四叉树分解,对于图像灰度值进行四叉树分解,并覆盖原图显示
八年级数学上册2.3等腰三角形典型例题练习新版湘教版.doc
SQL 例题 SQL 例题 SQL 例题 SQL 例题
高中地理 2.3大气的垂直分层和热力作用例题 湘教版必修1
几个方便理解的线段树例子··················
螺栓例题 考试都有 螺栓例题 例题螺栓例题 考试都有 螺栓例题 例题
sas例题复习,例题1, 例题2sas例题复习,例题1, 例题2sas例题复习,例题1, 例题2sas例题复习,例题1, 例题2sas例题复习,例题1, 例题2sas例题复习,例题1, 例题2sas例题复习,例题1, 例题2sas例题复习,例题1, 例题2...
数据库范式理解例题数据库范式理解例题
java 例题java 例题java 例题java 例题java 例题java 例题
决策树例题经典案例
事件树例题学习教案.pptx
解析几何:各种类型的分析,例题解答 历年例题
数学建模例题
常用算法及例题常用算法及例题常用算法及例题
线段树例题 唐文斌 noip联系题目 题目很经典 值得一看
oracle例题oracle例题oracle例题oracle例题oracle例题oracle例题oracle例题oracle例题oracle例题oracle例题
关于一些典型的线段树的例题,大家可以看一看,给一个评价,这些内容,后续我也会在博客上慢慢更新。希望大家多多的支持作者,谢谢! 这篇内容主要包含了一些我写的线段树的代码,可以帮助大家更好的理解线段树建树...