TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3600
  • 题目
  • P3600河中跳房子游戏
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    每年,奶牛们都举办一种特殊的跳房子游戏,在这个游戏中,大家小心翼翼地在河中的
    岩石上跳。这个游戏在一条笔直的河中进行,以一块岩石表示开始,以另一块距离起点L
    单位长度的岩石表示结束 (1 <= L <= 1,000,000,000)。在这两块岩石中间还有N
    (0 <= N <= 50,000) 块岩石,每块的位置距离起点是 Di (0 < Di < L)个单位长度。

    玩这个游戏的时候,每头牛从开始的那块岩石想办法要跳到表示结束的那块岩石上。中间
    只能在从某块岩石跳跃到另一块岩石,反复的这样跳。当然,不够敏捷的牛永远跳不到终点,
    最终只能落入河中。

    农民 John 为他的牛感到自豪,每年都观看比赛。随着时间的推移,他对于那些胆小的
    只能跳过很短距离的牛感到厌烦。为了那些牛,其他农民会把岩石的间距弄得很小。他
    计划移除一些岩石,从而增加奶牛在跳跃时需要的最短距离。他不能移除开始和结束的两块
    岩石。但是除此之外他可以移除 M (0 <= M <= N)块岩石。

    FJ 希望知道他能够增加多少最短跳跃距离。求当他移除了M块岩石后,奶牛从开始跳到结束
    的岩石,每次跳跃的最短距离至多可以增加到多少。

    输入格式

    行 1: 三个用空格分开的整数,分别是 L, N, 和 M

    行 2..N+1: 每行一个整数,表示中间N块岩石的位置,没有两块岩石处于同一位置。

    输出格式

    行 1: 一个整数表示移除某M块岩石后,相邻岩石间距最小值的最大可能情况。

    样例输入

    25 5 2 

    14 
    11 
    21 
    17 

    样例输出

    4

    提示

    样例解释:

    没有移除任何岩石之前,最少需要跳2个单位长度,从0到2。当移除了位于 2 和 14
    的两块岩石后, 需要的最短跳跃距离就变成了4。(从 17 到 21 或 从 21 到 25)。


    来源  USACO 2006 DEC SILVER