P3127 [USACO15OPEN]被困在haybales(金)Trappe…

    • 59通过
    • 153提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 并查集 枚举,暴力 离散化 USACO 2015 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    题目描述

    农夫约翰最近买了N个干草堆,他把这些干草堆都放在家和农场之间的一条直路上,每个干草堆的位置各不相同。不幸的是,他忘记了他的奶牛贝里斯正外出吃草,贝里斯也许会被这些干草堆所限制住!干草堆j的大小是Sj,在Pj的位置上。贝里斯从一个不是干草堆的地方出发,他可以自由的在这条直线上移动,他不能越过干草堆。有一种特殊的情况, 他可以往一个方向连续跑了D的距离以后,他就可以积累足够的能量,然后就可以消除小于D的干草堆。当然了,在消除了一个干草堆以后,他就可以有更多的空间来跑步和积蓄能量了。当贝里斯成功消除了第一个或者最后一个干草堆的时候,他就可以获得自由了,请你计算使得贝里斯不能获得自由的初始位置的区间总和。

    输入

    第一行是一个正整数N,表示干草堆的数量。接下来N行,每行两个正整数,分别表示干草堆的大小和位置。

    输出

    输出使得贝里斯不能获得自由的初始位置的区间总和。

    感谢@sxyugao 提供的翻译

    题目背景

    题目描述

    Farmer John has received a shipment of N large hay bales ($1 \le N \le 100,000$), and placed them at various locations along the road leading to his barn. Unfortunately, he completely forgets that Bessie the cow is out grazing along the road, and she may now be trapped within the bales! Each bale $j$ has a size $S_j$ and a position $P_j$ giving its location along the one-dimensional road. Bessie the cow can move around freely along the road, even up to the position at which a bale is located, but she cannot cross through this position. As an exception, if she runs in the same direction for $D$ units of distance, she builds up enough speed to break through and permanently eliminate any hay bale of size strictly less than $D$. Of course, after doing this, she might open up more space to allow her to make a run at other hay bales, eliminating them as well.

    Bessie can escape to freedom if she can eventually break through either the leftmost or rightmost hay bale. Please compute the total area of the road consisting of real-valued starting positions from which Bessie cannot escape.

    输入输出格式

    输入格式:

    The first line of input contains $N$. Each of the next $N$ lines describes a

    bale, and contains two integers giving its size and position, each in the range

    $1\ldots 10^9$. All positions are distinct.

    输出格式:

    Print a single integer, giving the area of the road from which Bessie cannot

    escape.

    输入输出样例

    输入样例#1: 复制
    5
    8 1
    1 4
    8 8
    7 15
    4 20
    输出样例#1: 复制
    14

    说明

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。