#1259. [USACO06DEC] River Hopscotch S

[USACO06DEC] River Hopscotch S

题目描述

奶牛们每年都会举办一次活动,内容是一种奇特的跳房子游戏,即在河中小心翼翼地从一块石头跳到另一块石头。比赛在一条笔直的长河上进行,起点有一块石头,终点有另一块石头,距离起点 LL 个单位(1≤L≤1,000,000,0001 \le L\le 1,000,000,000)。 在起点和终点岩石之间的河道上,会出现 NN 个(0≤N≤50,0000\le N\le 50,000 个)更多的岩石,每个岩石与起点的距离为一个整数 DiD_i($0

输入格式

第 11 行,三个空格分隔的整数:LL、NN 和 MM。

第 2…N+12\dots N+1 行,每行包含一个整数,表示某块岩石距离起始岩石的距离。 没有两块石头的位置相同。

输出格式

一个整数,即奶牛在移走 MM 块石头后所需跳跃的最短距离的最大值。

样例

25 5 2
2
14
11
21
17
4

题目来源:洛谷 P2855