要解决这个问题，我们需要在马拉松比赛的观察点安装最少的饮水机，使得所有观察员都能在其体力范围内取水。每个观察员的活动范围可以表示为一个区间，我们的任务是选择最少的点，使得每个区间至少包含一个点。

方法思路

1. 问题分析：每个观察员的活动范围可以表示为区间 [S - W, S + W]，其中 S 是观察点到起点的距离，W 是观察员的体力。我们需要找到最少的点，使得每个区间至少包含一个点。
2. 贪心算法：经典的区间覆盖问题，可以通过贪心算法解决。具体步骤是：
   • 将所有区间按右端点排序。
   • 每次选择当前未被覆盖的最左区间的右端点作为安装点，这样可以覆盖尽可能多的后续区间。

解决代码

n = int(input())
intervals = []
for _ in range(n):
    s, w = map(int, input().split())
    left = s - w
    right = s + w
    intervals.append((left, right))

intervals.sort(key=lambda x: x[1])
count = 0
last = -float('inf')
for left, right in intervals:
    if left > last:
        count += 1
        last = right
print(count)

代码解释

1. 输入处理：读取输入的观察点数和每个观察点的位置及体力。
2. 区间转换：将每个观察点的位置和体力转换为区间 [S - W, S + W]。
3. 排序：按区间的右端点升序排序。
4. 贪心选择：遍历排序后的区间，每次选择当前未被覆盖的最左区间的右端点作为安装点，更新覆盖范围并计数。

该方法确保在最少的安装点下覆盖所有区间，时间复杂度为 O(N log N)，主要来自排序操作。