CF545C.Woodcutters
普及/提高-
通过率:0%
时间限制:1.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Little Susie listens to fairy tales before bed every day. Today's fairy tale was about wood cutters and the little girl immediately started imagining the choppers cutting wood. She imagined the situation that is described below.
There are n trees located along the road at points with coordinates _x_1, _x_2, ..., x__n. Each tree has its height h__i. Woodcutters can cut down a tree and fell it to the left or to the right. After that it occupies one of the segments [x__i - h__i, x__i] or [x__i;x__i + h__i]. The tree that is not cut down occupies a single point with coordinate x__i. Woodcutters can fell a tree if the segment to be occupied by the fallen tree doesn't contain any occupied point. The woodcutters want to process as many trees as possible, so Susie wonders, what is the maximum number of trees to fell.
小苏西每天睡前都会听童话故事。今天的故事讲的是伐木工人,小女孩立刻开始想象伐木工人们砍伐树木的情景。她想象出了如下所述的情形:
道路上沿直线排列着 n 棵树,其位置坐标分别为 x1,x2,…,xn。每棵树的高度为 hi。伐木工人可以将一棵树砍倒,使其向左或向右倾倒。倾倒后,该树将占据区间 [xi−hi,xi](向左倒)或 [xi,xi+hi](向右倒)。未被砍倒的树仅占据一个点,即其原始位置 xi。伐木工人只有在倾倒后所占据的区间内不包含任何已被占据的点时,才允许砍倒该树。伐木工人希望尽可能多地砍倒树木,因此小苏西想知道:最多能砍倒多少棵树?
输入格式
The first line contains integer n (1 ≤ n ≤ 105) — the number of trees.
Next n lines contain pairs of integers x__i, h__i (1 ≤ x__i, h__i ≤ 109) — the coordinate and the height of the і-th tree.
The pairs are given in the order of ascending x__i. No two trees are located at the point with the same coordinate.
第一行包含一个整数 n(1≤n≤105)—— 树的棵数。
接下来的 n 行每行包含一对整数 xi,hi(1≤xi,hi≤109)—— 第 i 棵树的坐标和高度。
这些数对按 xi 的升序给出。不存在两棵树位于同一坐标点上。
输出格式
Print a single number — the maximum number of trees that you can cut down by the given rules.
输出一个整数——按照给定规则最多可以砍伐的树木数量。
输入输出样例
输入#1
5 1 2 2 1 5 10 10 9 19 1
输出#1
3
输入#2
5 1 2 2 1 5 10 10 9 20 1
输出#2
4
说明/提示
In the first sample you can fell the trees like that:
- fell the 1-st tree to the left — now it occupies segment [ - 1;1]
- fell the 2-nd tree to the right — now it occupies segment [2;3]
- leave the 3-rd tree — it occupies point 5
- leave the 4-th tree — it occupies point 10
- fell the 5-th tree to the right — now it occupies segment [19;20]
In the second sample you can also fell 4-th tree to the right, after that it will occupy segment [10;19].
在第一个样例中,你可以按如下方式砍倒树木:
- 将第 1 棵树向左砍倒——此时它占据线段 [ - 1;1]
- 将第 2 棵树向右砍倒——此时它占据线段 [2;3]
- 不砍第 3 棵树——它占据点 5
- 不砍第 4 棵树——它占据点 10
- 将第 5 棵树向右砍倒——此时它占据线段 [19;20]
在第二个样例中,你也可以将第 4 棵树向右砍倒,之后它将占据线段 [10;19]。
输入解题思路,AI测评打分。不知道怎么写?