夜雨聆风写在前面
本次给大家带来2026年8月9日科大讯飞笔试题的1道题，本场机考题目可在咱们平台上在线刷题。
第一题：将已有树转成覆盖区间并按左端点排序，贪心维护从 开始连续覆盖到的最右位置，遇到空缺时用长度为 的新覆盖区间尽可能向右补齐，最终统计最少新增树数。
塔子哥的配套刷题网站:codefun2000.com
第1题-巡检通道覆盖补点
题目描述
某园区中有一条长度为 的线性巡检通道，可以将整条通道表示为坐标区间 。为了保证沿线设备能够持续得到服务，通道附近已经部署了一批覆盖节点。
目前共有 个已有节点。第 个节点位于坐标 ，其覆盖半径为 ，因此它能够覆盖距离 不超过 的位置。
现在还可以增设若干个统一规格的新节点。每个新节点的覆盖半径均为 ，其部署位置可以根据需要确定。
需要使已有节点与新增节点的覆盖范围合在一起后，能够覆盖整个区间 。
请计算，为达到这一目标，最少需要新增多少个节点。
保证任意两个已有节点的位置均不相同。
输入描述
第一行输入三个整数 ，分别表示巡检通道的长度、已有节点的数量以及新节点的覆盖半径。
数据满足：
接下来 行，每行输入两个整数 ，表示第 个已有节点的位置及其覆盖半径。
数据满足：
并且所有 两两不同。
输出描述
输出一个整数，表示为了覆盖整条巡检通道，最少需要新增的节点数量。
样例1
输入
10 2 22 28 2输出
1说明
第一个已有节点能够覆盖通道上的 ，第二个已有节点能够覆盖 。
因此目前只有 这一段尚未得到完整覆盖。新增一个覆盖半径为 的节点即可补齐这部分区域，所以最少需要新增 个节点。
题解
解题思路
将每棵已有节点能够覆盖的范围转化为区间：
由于只需要覆盖通道 ，因此将区间限制在：
使用排序 + 贪心。
先按照已有区间的左端点从小到大排序，并维护变量 ，表示当前从 开始已经连续覆盖到的最右位置。
依次处理区间 ：
如果 ，说明这个区间完全位于已经覆盖的部分中，直接跳过。 如果 ，说明当前区间能够和已经覆盖的部分连接起来，将 更新为 。 如果 ，说明 之间存在未覆盖区域。每棵新节点最多能够连续覆盖长度 ，因此至少需要：
棵新节点。
为了让新增节点尽可能向右覆盖，直接从当前 开始连续放置这些节点。加入 棵后，可以将覆盖位置推进到：
随后再利用当前已有区间，将 更新为二者的较大值。
这种做法的核心是贪心：对于当前最左侧尚未覆盖的位置，一棵新节点在覆盖它的前提下，应当尽可能向右放置，这样能够覆盖最远的位置，不会使后续情况变差。
所有已有区间处理完成后，如果还有 没有覆盖，再补：
棵节点即可。
需要注意，不能简单将所有未覆盖区间分别计算答案后相加。因为一棵新增节点可能跨过一段已经被旧节点覆盖的区域，同时覆盖其左右两侧，因此必须按照上述方式维护连续覆盖到的最右位置。
复杂度分析
对 个已有覆盖区间进行排序，时间复杂度为 。
之后只需要线性遍历一次，时间复杂度为 。
因此总时间复杂度为：
存储 个区间，空间复杂度为：
在 的数据范围内可以顺利通过。
代码实现
python代码(C++和JAVA代码见在线OJ网址)
defmin_trees(L, m, D, trees): intervals = []# 将已有节点转化为覆盖区间for x, c in trees: left = max(0, x - c) right = min(L, x + c) intervals.append((left, right))# 按左端点排序 intervals.sort() right = 0 ans = 0 length = 2 * Dfor left, end in intervals:# 当前区间已经完全被覆盖if end <= right:continue# 中间存在空缺，需要新增节点if left > right: need = (left - right + length - 1) // length ans += need right += need * length# 利用已有区间继续向右扩展if end > right: right = endif right >= L:break# 处理最后剩余的未覆盖部分if right < L: ans += (L - right + length - 1) // lengthreturn ansdefmain(): L, m, D = map(int, input().split()) trees = []for _ in range(m): x, c = map(int, input().split()) trees.append((x, c)) print(min_trees(L, m, D, trees))if __name__ == "__main__": main()