题目名称 | 3006. [POJ 2374]围栏障碍训练 |
---|---|
输入输出 | fence_obstacle.in/out |
难度等级 | ★★☆ |
时间限制 | 1000 ms (1 s) |
内存限制 | 256 MiB |
测试数据 | 9 |
题目来源 | syzhaoss 于2018-10-23加入 |
开放分组 | 全部用户 |
提交状态 | |
分类标签 | |
分享题解 |
通过:0, 提交:0, 通过率:0% | |||
关于 围栏障碍训练 的近10条评论(全部评论) |
---|
fence_obstacle.in
输出文件:fence_obstacle.out
简单对比农夫约翰为他的奶牛们建造了一个围栏障碍训练场,以供奶牛们玩耍。
训练场由 N 个不同长度的围栏组成,每个围栏都与 x 轴平行,并且第 i 个围栏的 y 坐标为 i。
训练场的出口位于原点,起点位于 (S,N)
+-S-+-+-+ (fence #N) +-+-+-+ (fence #N-1) ... ... +-+-+-+ (fence #2) +-+-+-+ (fence #1) =|=|=|=*=|=|=| (barn) -3-2-1 0 1 2 3
这些牛会从起点处开始向下走,当它们碰到围栏时会选择沿着围栏向左或向右走,走到围栏端点时继续往下走,按照此种走法一直走到出口为止。
请问,这些牛从开始到结束,行走的水平距离最少为多少。
第一行包含两个整数 N 和 S。
第 2..N+1 行,每行包含两个整数 Ai,Bi,表示一个围栏的起始横坐标和结束横坐标,其中第 i+1 行表示第 i 个围栏的数据。
起点坐标满足 AN≤S≤BN。
输出一个整数,表示最小水平行走距离。
4 0 -2 1 -1 2 -3 0 -2 1
4
$1\leq N\leq 30000,-10^5\leq S\leq 10^5,-10^5\leq A_i,B_i\leq 10^5$。