林品逸
(hyacinth_lpy)
1
砍树king
题目描述：
大哈参加了一档叫做"砍树king"的比赛, 他面前有一排树, 第i棵树的坐标是xi, 以及它们的长度hi。
树可以往左倒，也可以往右倒，但是要求砍倒的树不能重合，也不能覆盖其他的树原来的位置。
求大哈最多可以砍倒多少棵树。
输入格式：
第一行输入一个整数n(1<=n<=100000)
接下来n行，每行两个整数xi,hi(1<=xi,hi<=1000000000)
输入保证xi为升序。
输出格式：
输出最多可以砍倒多少棵树
样例输入1：
5
1 2
2 1
5 10
10 9
19 1
样例输出1：
3
5 个赞
袁少
(烈焰·行仓)
3
左倒：判断高度是否小于等于“与前一棵树的距离”，成立ans++
否则右倒：判断高度是否小于等于“与后一棵树的距离”，成立ans++，且该数位置加上其高度
2 个赞
陈柏衡
(陈柏衡)
4
G. 砍树king
策略：
每棵树能往左倒就往左倒，如果往左倒不下，能往右倒就往右倒。
简单论证：
如果所有的树都能往左倒，直接就可以满足题目要求
而如果对于某个第 i 棵树来说，它不能够往左倒：
如果 x[i] + h[i] >= x[i + 1]，说明也不能往右倒
如果 x[i] + h[i] <= x[i + 1]，说明此时有两种选择，
- 往右倒。如果往右倒后，第 i + 1 棵树还是能往左倒，那最好；如果往右倒后，第 i + 1棵树不能往左倒了，此时答案也不会更差。因为在这段区间里，要不是第 i 棵树倒，要不是第 i + 1棵树倒，对答案的贡献都是1。
- 不往右倒。可能使答案变小，所以不能往右倒。
求解决方案
1 个赞