问题1637--砍树问题

1637: 砍树问题

时间限制: 1 Sec  内存限制: 128 MB
提交: 8  解决: 4
[提交] [状态] [讨论版] [命题人:]

题目描述

水平马路上种了n棵树，每棵树都可以看作是一条位置为pi，长度为ai的竖线段。
如果有两颗树i,j。若i顶端与j底端连线的倾角大于45°，我们就认为i挡住了j。
现在要将一些树砍低，使得不存在挡住的情况，他想知道总共最少需要砍掉多少长度。请你来帮他计算一下。
注：若同一位置有两棵树，那么这两棵树当且仅当高度均为0时，才能保证它们不互相挡住。

输入

第一行一个正整数n。
接下来n行，每行两个正整数pi,ai，表示一棵树的位置和高度。

输出

输出一个数，表示最少砍断多少长度。

样例输入 Copy 

3
0 2
1 2
3 3

样例输出 Copy 

3

来源/分类

枚举算法 贪心算法 
[提交] [状态]