| 题目名称 | 2209. [USACO US open15] 困在草堆(金组) |
|---|---|
| 输入输出 | trapped.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 15 |
| 题目来源 |
 Satoshi
于2016-04-05加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：7， 提交：12， 通过率：58.33% | ||||
 WangYenJen |
100 | 1.343 s | 15.57 MiB | C++ |
 zhengtn03 |
100 | 1.864 s | 3.36 MiB | C++ |
 MiracleEEEE |
100 | 1.900 s | 1.83 MiB | C++ |
|
MiracleEEEE |
100 | 1.901 s | 1.83 MiB | C++ |
|
zhengtn03 |
100 | 2.135 s | 4.52 MiB | C++ |
|
zhengtn03 |
100 | 2.546 s | 5.65 MiB | C++ |
 Satoshi |
100 | 4.553 s | 3.14 MiB | C++ |
|
MiracleEEEE |
46 | 1.904 s | 1.83 MiB | C++ |
|
zhengtn03 |
46 | 2.061 s | 5.65 MiB | C++ |
|
MiracleEEEE |
40 | 0.373 s | 1.82 MiB | C++ |
| 关于 困在草堆(金组) 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
证明：
Sort the haybales by location. Consider two haybales i and j such that Bessie can start somewhere between those haybales and break through all the haybales from i+1 to j−1, but she can't break haybale i or haybale j. It must be the case then that no haybale between i and j is strictly taller than those two. That motivates the following O(NlogN)solution: Sort the haybales in decreasing order of size. Consider having an empty road, and place the haybales in that order. When placing a haybale, look immediately to its left and to its right and see if you can break through either one of those haybales if you were inside that interval. Mark that interval as "trapped" if so. This will be O(NlogN) as long as you check to make sure that the interval isn't already marked as trapped. 按重量从大到小排序，可以保证区间不会被漏掉 | ||||
【题目描述】
$FJ$装运了$N$捆干草，把它们放到了通往谷仓的道路上的不同位置。不幸的是，
他完全忘记了$Bessie$正在这条道路上吃草，她有可能已经困在了草堆里！
每个草堆$j$有大小$S_j$和位置$P_j$表示一维道路上的方位。$Bessie$可以在这条道路上自由的移动，甚至包括有草堆的地方，但是她不能穿过草堆，作为例外，如果她朝着同一个方向连续奔跑了$D$个单位，她就有足够的速度穿过草堆并且永久的消除这个草堆（当这个草堆的大小$S_i<D$）。当然，在这之后，她可以有更大的空间来冲向另一个草堆，也把它消除.
如果$Bessie$最后消除了最左边或者最右边的草堆，她就可以逃出道路，获得自由.
一个围困位置表示如果$Bessie$从这个点出发将不能逃出道路，请计算围困位置的总长度.
【输入格式】
第一行一个正整数$N$
接下来$N$行每行两个正整数，表示$S_j$和$P_j$
【输出格式】
只有一行一个整数，为围困位置的总长度
【样例输入】
58 1 1 4 8 8 7 15 4 20
【样例输出】
14
【样例解释】
以下为译者自己添加的内容，方便读者理解(但是实际上透漏了部分题解)，但是原题并没有，如果实在是读不懂题意再看这些内容。
草堆大小$S_j$:8 1 8 7 4
草堆位置$P_j$:1----4----8----15----20
如果Bessie在1---4内，所能产生的最大速度为3,比8小比1大，只能穿过位置4的草堆并消除这个草堆，然后Bessie在1---8内，所能产生的最大速度为8,都不比8大，所以Bessie被困在了1---8,
如果Bessie在4---8内，所能产生的最大速度为4,比8小比1大，只能穿过位置4的草堆并消除这个草堆，然后Bessie在1---8内，所能产生的最大速度为8,都不比8大，所以Bessie被困在了1---8,
如果Bessie在8---15内，所能产生的最大速度为7,比8小不比7大，不能穿过任何草堆
如果Bessie在15---20内，所能产生的最大速度为5,比4大，直接从右边逃走
综上可知，Bessie在1-15内不能逃走，所以围困位置的总长度为14
【数据范围】
对于26.67%的数据,$N<=4000$（铜难度）
对于33.33%的数据,$N<=32000$
对于100%的数据,$N<=100000(金难度),0<=S_j,P_j<=10^9$,所有$P_j$两两互不相同
【来源】
USACO 2015 US open Gold