Skip to content

11581: 【原1581】奔跑吧保祥

题目

题目描述

author: Spy 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1581

Description

保祥是一只想学习视频后期的摄影师,他的理想是成为阿联酋酋长。为了实现这一目标,他最近开始跑步。 为了支持奔跑的保祥追寻梦想,学校推出了一款APP,APP中预设了不同的跑步路径供保祥选择,每一种路径中会自动生成不同的感应位点。

保祥是个不喜欢拐弯抹角的人,因此他选择沿着笔直的宣怀大道跑步,APP为他规定了跑步的起点和终点。在起点和终点之间,有 N 个位点(不含起点和终点)。跑步时,保祥必须按次序经过每一个位点,最终到达终点。

为了减少中途找点的次数,提高跑步质量,APP设计者计划删除一些位点,使得路径中相邻两个位点间的最短距离尽可能长。设计者计划至多从起点和终点之间删除 M 个位点(不能删除起点和终点)。

Input Format

输入第一行包含三个整数 L,N,M,分别表示起点到终点的距离,起点和终点之间的位点数,以及设计者至多删除的位点数。

接下 N 行,每行一个整数,第 i 行的整数 Di(0<Di<L)表示第 i 个位点与起点的距离。这些位点按与起点距离从小到大的顺序给出,且不会有两个位点出现在同一个位置。

Output Format

输出只包含一个整数,即相距最近的相邻两个位点间距离的最大值。

Sample Input

25 5 2
2
11
14
17
21

Sample Output

4

Limits

  • 对于20%的数据,0≤M≤N≤10。
  • 对于50%的数据,0≤M≤N≤100。
  • 对于100%的数据,0≤M≤N≤50000,1≤L≤1000000000。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!