TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1357
  • 题目
  • P1357跨栏课程 (做了1361再做此题)
    限制 : 时间限制 : 20000 MS   空间限制 : 65536 KB
    问题描述

    农民john为奶牛们设计了一个运动课程。他在课程里面设置了N个不同长度的围栏 (1 <= N <= 50,000),每条围栏都平行
    于x坐标轴。第i条围栏的y坐标就是i。
    谷仓的大门位于坐标原点(也就是下图的"*"位置)。运动课程的起点坐标为(S,N)

    john原打算让奶牛们奔跑跨过这些围栏,但是奶牛们更加喜欢慢步。所以,奶牛们总是沿着围栏走,当走到一条围栏的尽
    头时,它们会转向,然后沿着垂直于x轴的方向向x轴走近,直到它们受到了另一条围栏或者是谷仓的墙壁的阻挡。这时它
    们会决定往左还是往右走,直到到达了围栏的尽头。如此重复,直到它们最终到达了谷仓的大门。

    奶牛们想尽量少走路,请找出从起点到谷仓大门的最短距离(注:x轴上经过的最短距离)。

    输入格式

    第一行,两个空格间隔的整数N和S(-100,000 <= S <= 100,000)
    第2行到第N+1行,每行两个空格间隔的整数: A_i 和 B_i (-100,000 <= A_i < B_i <= 100,000)表示第i条围栏的起点的x坐标和终点的x坐标
    A_N <= S <= B_N

    输出格式

    一个整数,表示从起点到终点在x轴方向上经过的最短距离(y轴方向经过的距离不用考虑,因为距离就是N)

    样例输入

    4 0 
    -2 1
    -1 2
    -3 0
    -2 1

    输入说明:

       +-+-S-+             围栏 4

     +-+-+-+               围栏 3

         +-+-+-+           围栏 2

       +-+-+-+             围栏 1

     |=|=|=*=|=|=|         谷仓

    -3-2-1 0 1 2 3      

    样例输出

    4

    提示

    输出说明:
    从第4条围栏开始,沿x轴正方向走到(1,4),然后转向沿垂直于x轴方向往x轴走。走到第2条围栏时沿x轴正方向走到(2,2)。

    然后转向往谷仓方向走。到达谷仓墙壁后沿x轴反方向走向源点。


    来源  USACO 2004 December Gold