首页 > 试题广场 >

校门外的树

[编程题]校门外的树
  • 热度指数：6487 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}某校大门外长度为 L 的马路上有一排树，每两棵相邻的树之间的间隔都是 1 米。我们可以把马路看成一个数轴，马路的一端在数轴 0 的位置，另一端在 L 的位置；数轴上的每个整数点，即 0,1,2,\dots,L，都种有一棵树。

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

输入描述:
\hspace{15pt}第一行输入两个整数 L,M，用空格隔开，表示马路的长度和地铁施工区域数，满足 1 \leqq L \leqq 10000，1 \leqq M \leqq 100。

\hspace{15pt}接下来 M 行，每行输入两个整数 l_i,r_i，用空格隔开，表示第 i 个施工区域的起始点和终止点的坐标，满足 0 \leqq l_i \leqq r_i \leqq L。


输出描述:
\hspace{15pt}输出一个整数，表示移除所有施工区域内（包括端点）树后，剩余的树的总棵树数。
示例1

输入

500 3
150 300
100 200
470 471

输出

298

说明

马路上共有 L+1=501 棵树。施工区域 [150,300] 中含有 151 棵，[100,200] 中含有 101 棵，[470,471] 中含有 2 棵。三个区域的重叠部分 [150,200] 有 51 棵被重复移除，所以实际移除的树数为 151+101+2-51=203，因此剩余 501-203=298 棵。
示例2

输入

10 2
2 5
4 8

输出

4

说明

马路上共有 11 棵树。区域 [2,5] 移除 4 棵，区域 [4,8] 移除 5 棵。重叠部分 [4,5] 有 2 棵被重复移除，所以实际移除 4+5-2=7 棵，剩余 11-7=4 棵。

备注:

算法知识视频讲解
开通博客
头像 平凡的小白
发表于 2020-05-29 14:55:48
思路：能暴力就先先一下暴力，题目差不多就会一半了。1.每次输入左右区间就把数组对应位置+1表示这棵树被移走，重复的部分多次+1不要紧，我们的结果是有多少个元素值是0。2.，好像不会超时，考虑更优的做法。差分+前缀和1.给一个区间加上一个值，我们只要考虑两个端点，中间的元素不需要考虑。2.前缀和，理解 展开全文
去ta的博客 赞 (21) 回复(1) 收起
头像 未知^_~
发表于 2020-05-22 17:35:31
前缀和与差分解法(适合数据量大时候使用) #include<iostream> using namespace std; const int N = 10010; int l,m,x,y,sum; int q[N],s[N]; int main() { cin>> 展开全文
去ta的博客 赞 (10) 回复(0) 收起
头像 sunrise__sunrise
发表于 2020-05-21 21:34:49
差分 模拟太简单了，我就不说了，直接说差分，适用数据可以开下数组的时候对于给的左右区间，直接把左端点减1，右端点后面一个点+1。最后再进行一次求前缀和，即可得到原来的区间各个值，值为0的就是存在树的点，注意一下区间范围 #include <bits/stdc++.h> #pragma 展开全文
去ta的博客 赞 (9) 回复(1) 收起
头像 虽然吧_但是
发表于 2020-05-21 20:28:01
这数据O(n^2) 模拟 ，我不想tle看区间，区间覆盖的贪心，多想想，人总是贪心的 思路： 不妨把左端点从小到大排序，此时就是把覆盖的区间进行合并 比如合并过后区间是[l1,r2]但要注意像下面这种情况 第一个区间包含第二个区间 此时我们就无需改变右指针所以right=max(a[i].r,ri 展开全文
去ta的博客 赞 (8) 回复(0) 收起
头像 禊月初三
发表于 2025-07-07 15:37:34
L, M = map(int, input().split()) trees = [1] * (L + 1) for i in range(M): a, b = map(int, input().split()) for j in range(a, b + 1): 展开全文
去ta的博客 赞 (8) 回复(0) 收起
头像 安和桥北_
发表于 2021-12-30 23:34:21
雨巨无敌 方法一：差分 对m个区域进行差分数组delta [ i ]维护 本质上是 如果有一个区间砍树 相应的原数组就+1。 在差分数组上表现为 区间左端点 +1 区间右端点的下一个 -1 维护好这个数组后 求差分数组的前缀和 得到原数组a [ i ]即可 判断是否等于0 如果等于0 代表没有被砍 展开全文
去ta的博客 赞 (8) 回复(0) 收起
头像 牛奶烧仙草
发表于 2021-11-16 19:57:47
C语言，一个超级简单的方法，开一个数组（马路长度）全为零,地铁过的地方全为1，树棵数减掉地铁过的地方就行了。 ```#include<stdio.h> int main () { int l=0; int n=0; int i,j,k; int a=0,b=0; int sum 展开全文
去ta的博客 赞 (7) 回复(1) 收起
头像 chinaboy
发表于 2020-08-03 11:57:36
第一个数据范围 L（1 <= L <= 10000）和 M（1 <= M <= 100）//简单模拟即可 有树为1，无树为0，最后遍历统计1的个数代码如下： #include<stdio.h>//模拟 #include<string.h> 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 那万一赢了呢
发表于 2020-08-11 20:57:17
思路：因为给的区域有重合部分所以可以将注意从移走多少树变为剩多少树。步骤：创建一个给定长度的数组并赋初值为0，给一个区域就用for循环将其减一，再用for循环遍历一遍为0的就是有树的。 #include "stdio.h" #include "iostream" using namespace st 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 活泼泼
发表于 2021-03-27 11:42:14
如果这题道路长1e9，数组开不下，就可以进行离散化处理：记录每次输入的左右端点，将这些点编号，并按照所在位置大小排序。最后遍历完这些点，统计出没砍掉的区间里有多少树。左端点的position记为1，右端点记为-1.一段区间没砍掉，当且仅当它左边的左端点个数等于右端点个数因此可以用一个变量sum来记录 展开全文
去ta的博客 赞 (3) 回复(0) 收起

问题信息

NOIP复赛 枚举
难度：
27条回答 626浏览

热门推荐

通过挑战的用户

查看代码

相关试题

校门外的树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号