← 返回题单

题单练习贪心

← 上一题下一题 →

A5431 | $Woodcutters$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

小 Susie 每天睡前都会听童话故事。今天的故事讲的是伐木工人，小女孩立即开始想象伐木工人砍树的场景，她想象出了如下描述的情景。 有 $n$ 棵树沿公路排列，它们分别位于坐标 $x_{1}, x_{2}, ..., x_{n}$ 处。每棵树的高度为 $h_{i}$。伐木工人可以砍倒一棵树，使其向左或向右倒下。倒下后，树将占据区间 $[x_{i} - h_{i}, x_{i}]$ 或 $[x_{i}, x_{i} + h_{i}]$。未倒下的树只占据 $x_{i}$ 这一个点。如果被倒下的树所占据的区间内没有任何已被占据的点，则可以砍倒这棵树。伐木工人想要砍倒尽可能多的树，Susie 想知道最多可以砍倒多少棵树。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 10^{5}$），表示树的数量。 接下来的 $n$ 行，每行包含一对整数 $x_i, h_i$（$1 \le x_i, h_i \le 10^{9}$），表示第 $i$ 棵树的坐标和高度。 这些对数以 $x_i$ 升序给出。不会有两棵树处于相同的坐标。

输出格式

输出一个整数，表示按照上述规则最多可以砍倒多少棵树。

输入输出样例

输入 #1

输出 #1

输入 #2

输出 #2

C++ 编辑器

输入

输出