NKOI3600 河中跳房子游戏

河中跳房子游戏"/>

NKOI3600 河中跳房子游戏

[二分答案]

题目描述

每年，奶牛们都举办一种特殊的跳房子游戏，在这个游戏中，大家小心翼翼地在河中的岩石上跳。这个游戏在一条笔直的河中进行，以一块岩石表示开始，以另一块距离起点L单位长度的岩石表示结束 (1 <= L <= 1,000,000,000)。在这两块岩石中间还有N(0 <= N <= 50,000) 块岩石，每块的位置距离起点是 Di (0 < Di < L)个单位长度。
玩这个游戏的时候，每头牛从开始的那块岩石想办法要跳到表示结束的那块岩石上。中间只能在从某块岩石跳跃到另一块岩石，反复的这样跳。当然，不够敏捷的牛永远跳不到终点，最终只能落入河中。FJ计划移除一些岩石，从而增加奶牛在跳跃时需要的最短距离。他不能移除开始和结束的两块岩石。但是除此之外他可以移除 M (0 <= M <= N)块岩石。FJ 希望知道他能够增加多少最短跳跃距离。求当他移除了M块岩石后，奶牛从开始跳到结束的岩石，每次跳跃的最短距离至多可以增加到多少。

输入格式

行 1: 三个用空格分开的整数，分别是 L, N, 和 M
行 2..N+1: 每行一个整数，表示中间N块岩石的位置，没有两块岩石处于同一位置。

输出格式

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

这道题显然应该先按每个点到起点的距离排个序。