首页 > 试题广场 >

校门外的树

[编程题]校门外的树
  • 热度指数：12179 时间限制：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 棵。

备注:

算法知识视频讲解
添加回答
Python3
意若久时天然呆头像 意若久时天然呆 
L, M = map(int, input().split())
t = [1] * (L + 1)
for _ in range(M):
    l, r = map(int, input().split())
    for j in range(l, r + 1):
        t[j] = 0
print(sum(t))

发表于 2025-11-04 16:18:18 回复(0)
Python3
鼣人头像 鼣人
L, M = map(int, input().split())
# 初始化所有树都在
trees = [1] * (L + 1)  # 1表示有树，0表示被移走
for i in range(M):
    start, end = map(int, input().split())
    # 把这段区间的树都移走（标记为0）
    for j in range(start, end + 1):
        trees[j] = 0

shengyu_trees = sum(trees)
print(shengyu_trees)
正常施工路段应该不会重合吧
发表于 2025-09-26 11:22:07 回复(0)
Python3
牛客940035856号头像 牛客940035856号
l ,m = map(int,input().split())
#马路所有的树
n = [i for i in range(l+1)]
for j in range(m):
    l1 , r = map(int,input().split())
    #区域中的树
    nl = [y for y in range(l1,r+1)]
    for x in nl:
        if x in n:
            n.remove(x)
        else:
            pass
print(len(n))
复杂度比较高
发表于 2025-07-21 15:22:06 回复(0)
Python3
LI005头像 LI005
diff
L, M = map(int, input().split())
count = 0
cur = 0
diff = [0] * (L+2)

for i in range(M):
    li, ri = map(int, input().split())

    diff[li] = diff[li] + 1
    diff[ri + 1] = diff[ri + 1] -1

for j in range(L+1):
    cur = cur + diff[j]
    if cur == 0:
        count += 1

print(count)



///set
L, M = map(int, input().split())
total= L+1
cut = set()

for i in range (M):
    li, ri = map(int, input().split())

    for j in range (li, ri+1):
        cut.add(j)

remain = total - len(cut)

print(remain)
发表于 2025-07-15 20:43:40 回复(0)
Python3
禊月初三头像 禊月初三 
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):
        trees[j] = 0

print(sum(trees))


发表于 2025-07-07 15:38:40 回复(2)
Python3
想回学校的牛油少糖去冰头像 想回学校的牛油少糖去冰
n,M=map(int,input().split())
L=[1]*(n+1)
for _ in range(M):
    l,r=map(int,input().split())
    for i in range(l,r+1):
        L[i]=0
print(sum(L))
发表于 2025-06-24 16:16:05 回复(0)
提交观点

问题信息

NOIP复赛 枚举
难度：
9条回答 1164浏览

热门推荐

通过挑战的用户

查看代码

相关试题

校门外的树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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