蓝桥杯-跳石头

"""
https://www.lanqiao.cn/problems/364/learning/?page=1&first_category_id=1&problem_id=364
"""
L, N, M = map(int, input().split())
D = []
for i in range(N):
  D.append(int(input()))

# 判断最短跳跃距离为x时是否满足要求
def check(x):
  # 什么是合法? 当最短跳跃距离为x时, 移走岩石数量是否不超过M个
  # 当前石头与起点的距离now_idx, 移除数量: cnt
  now_idx = 0
  cnt = 0
  for i in range(N):
    # 此时这块石头跳跃距离小于x, 违反假设, 所以需要移除
    if D[i] - now_idx < x:
      cnt += 1
    else:
      now_idx = D[i]
  # 特判: 最后一个石头跳到终点的距离不能小于x
  if L - now_idx < x:
    return False
  return cnt <= M

ans = 1

# 二分答案
left, right = 1, L
while left <= right:
  mid = (left + right) // 2
  if check(mid):
    ans = mid
    left = mid + 1
  else:
    right = mid - 1
print(ans)