首页 > 试题广场 >

校门外的树

[编程题]校门外的树

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

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

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

输入描述:

第一行输入两个整数 ，用空格隔开，表示马路的长度和地铁施工区域数，满足 ，。

接下来  行，每行输入两个整数 ，用空格隔开，表示第  个施工区域的起始点和终止点的坐标，满足 。

输出描述:

输出一个整数，表示移除所有施工区域内（包括端点）树后，剩余的树的总棵树数。

示例1

输入

输出

说明

马路上共有  棵树。施工区域 [150,300] 中含有  棵，[100,200] 中含有  棵，[470,471] 中含有  棵。三个区域的重叠部分 [150,200] 有  棵被重复移除，所以实际移除的树数为 ，因此剩余  棵。

示例2

输入

10 2
2 5
4 8

输出

说明

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

备注:

算法知识视频讲解

Python 3

想顺利毕业的肱二头肌向光而行

方法1（暴力）：

把所有区间遍历，在区间内的树去除，否则保留。

import sys
 
L, M = map(int, sys.stdin.readline().strip().split())
T = [1] * (L + 1)
l_r=[]
for _ in range(M):
    i = list(map(int, sys.stdin.readline().strip().split()))
    l_r.append(i)
 
for l, r in l_r:
    for i in range(l,r+1):
        T[i]=0
 
print(sum(T))

方法2（差分数组法）：

用区间的标记代替区间的修改

import sys
 
L, M = map(int, sys.stdin.readline().strip().split())
diff = [0]*(L+2)
 
for _ in range(M):
    l, r = map(int, sys.stdin.readline().strip().split())
    diff[l]+=1
    diff[r+1]-=1
 
tree_count, count = 0, 0
for i in range(L+1):
    tree_count += diff[i]
    if tree_count == 0:
        count += 1
 
print(count)

方法3（合并数组）：
将被移除的区间合并。

1.区间排序：将所有区间按照左端点进行排序，方便后续操作。

2.判断合并：

(1) 能合并的情况：完全重叠（包含关系），部分重叠（有交集），区间相邻（题目要求端点处的树也要删除）。

(2) 不能合并的情况：因为已经按照左端点排序，只需要判断已判断区间右端点和未判断区间左端点的大小。

3.计算最终结果：全部树 - 移除区间中的树

import sys

L, M = map(int, sys.stdin.readline().strip().split())
intervals = [tuple(map(int, sys.stdin.readline().strip().split())) for _ in range(M)]

intervals.sort()
merged=[]

for l, r in intervals:
    if not merged&nbs***bsp;l > merged[-1][1] + 1:
        merged.append([l, r])
    else:
        merged[-1][1] = max(merged[-1][1], r)

removed = sum(r - l + 1 for l, r in merged)

print(L + 1 - removed)

发表于 2025-12-23 12:06:22 回复(0)

Python 3

牛牛大王不怕苦难

l, m = map(int, input().split(" "))
node_lst = []
flag = 0
cnt = 0
for i in range(0, m):
    x, y = map(int, input().split(" "))
    node_lst.append([x, 1])
    node_lst.append([y, -1])
    node_lst.sort()

start_node = node_lst[0][0]
for j in range(0, len(node_lst)):
    flag = flag + node_lst[j][1]
    if flag == 0:
        end_node = node_lst[j][0]
        yc_cnt = end_node - start_node + 1
        cnt += yc_cnt
        if j + 1 < len(node_lst):
            start_node = node_lst[j + 1][0]
print(l - cnt + 1)

发表于 2025-12-19 16:09:23 回复(0)

Python 3

K1m4stx

L, M = map(int, input().split())

S = []

for i in range(M):

temp = list(map(int, input().split()))

S.append(temp)

S.sort(key=lambda x: x[0])

# print(S)

L = L+1

for i in range(M):

if i==0:

L = L-(S[i][1]-S[i][0]+1)

else:

if S[i][0]<=S[i-1][1]:

if S[i][1]<S[i-1][1]:

S[i][1] = S[i-1][1]

else:

L = L - (S[i][1]-S[i-1][1])

else:

L = L-(S[i][1]-S[i][0]+1)

print(L)

发表于 2025-06-18 01:35:36 回复(0)

提交观点

问题信息

NOIP复赛枚举

难度：

4条回答 291收藏 1653浏览

通过挑战的用户

查看代码

全马破三

2022-12-28 13:14:38
WaterYi

2022-11-23 10:16:32
Wilson_...

2022-11-17 21:20:06
Acmer-ly

2022-04-04 16:29:20
多多捞捞菜菜

2022-03-21 14:06:43

校门外的树

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

备注:

问题信息

热门推荐

通过挑战的用户

相关试题