g5-09160. 搬石头 未做

一条登山步道从起点 $0$ 通往终点 $L$(单位:米),中间立着 $n$ 块石块,第 $i$ 块位于坐标 $x_i$,按升序给出,且与起点终点互不重合。起点与终点是观景台标记,不可移动;志愿者最多搬走 $m$ 块中间石块。搬完后,剩余石块连同两端形成一列相邻间距,请求出让相邻间距最小值尽可能大的方案,并输出这个最小间距的最大值。

第一行三个整数 $L,n,m$。
第二行 $n$ 个升序整数 $x_i$。

一行一个整数,表示最大化的相邻间距最小值。

试 $6$:搬走坐标 $5$ 与 $21$ 的两块,保留 $10,16,25$,与两端形成间距 $10,6,9,6$,最小为 $6$,只搬 $2$ 块,可行。试 $7$:从终点倒推,上一保留块须不超过 $31-7=24$,只能取 $21$;再往前须不超过 $14$,只能取 $10$;再往前须不超过 $3$,没有;即至多保留 $2$ 块,须搬走 $3$ 块,超过 $2$,不可行。故答案为 $6$。

$0\le m\le n\le 5\times 10^4$;$1\le L\le 10^9$;$0<x_1<x_2<\cdots <x_n<L$。