【砍树】

题目描述

小A在一条水平的马路上种了 n 棵树,过了几年树都长得很高大了,每棵树都可以看作是一条长度为 a[i] 的竖线段。由于有的树过于高大,挡住了其他的树,使得另一些树得不到阳光。如果有两棵树 i、j,那么 i 顶端与 j 底端连线的倾角大于 45 度(连线与地面的夹角),我们就定义为 i 挡住了 j 。现在小 A 希望将一些树砍低,使得不存在挡住的情况。他想知道总共最少需要砍掉多少长度,请你来帮他计算一下。

注意,如果同一位置有两棵树的话,根据题意,我们只能将这两棵树都砍成高度为 0 才能保证它们不相互挡住,但是高度为 0 并不代表这棵树不存在。

输入格式

第一行一个正整数 n ,表示有 n 棵树。
接下来 n 行,每行两个正整数 p[i],a[i] ,表示一棵树的位置和高度。

输出格式

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

样例数据 1

输入

3
0 2
1 2
3 3

输出

3

备注

【数据范围】
对于 50% 的数据,n≤100
对于 100% 的数据,n≤100000, 0<p[i], a[i]≤10000

先按树的位置排个序,对于每棵树,限制它的条件只有旁边两棵树。证明:对于3棵树 1 2 3 若要砍树3只需砍到h[3]=dis[2][3]为止,而1跟3的距离比2跟3的距离长,我们是从1,2合法的情况推过来的,既然h[3]=dis[2][3],则h[3]<dis[1][2]+dis[2][3]=dis[1][3],得证。

下面是代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*