TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • 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