#P1336. 2023.05.26-实习-第一题-多多的骨牌
2023.05.26-实习-第一题-多多的骨牌
![](https://s3.bmp.ovh/imgs/2024/09/03/9ec1757951030a02.jpg)
塔子哥穿越到战国时期,成为了一名将军。这天塔子哥在操练士兵,塔子哥在一条直线上安排了 n 名士兵,假设这些士兵只考虑高度,不考虑宽度,第 i 名士兵在位置 xi,其高度为hi,塔子哥可以任意选择一些士兵,命令其按顺序向左或者向右卧倒,向左卧倒之后会占据[xi - hi,xi]个位置,向右卧倒后会占据[xi, xi+hi]位置。要求卧倒的士兵不能触碰到其他之前已经卧倒的士兵或者站立的士兵。问塔子哥最多可以命令多少个士兵卧倒。
输入第一行为一个数字 n(1 ≤ n ≤ 105),表示有n个士兵。
接下来n行,每行输入两个数字xi和hi(0 ≤ xi ≤ 109,1 ≤ hi ≤ 109),表示第 i 个士兵的位置和高度。
输入保证 xi递增且不会出现相等的情况。
输出一个整数ans,表示最多能卧倒的士兵数。
输入
3
1 1
2 1
3 1
输出
2
说明
先让第一个士兵往左卧倒。再让第三个士兵往右卧倒。第二个士兵无论往左还是往右,都会触碰到其他士兵。
输入
5
15 37
42 12
45 7
51 34
94 33
输出
4
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.