# P2678 [NOIP 2015 提高组] 跳石头

## 题目背景

NOIP2015 Day2T1

## 题目描述

一年一度的“跳石头”比赛又要开始了！

这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 $N$ 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。

为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 $M$ 块岩石（不能移走起点和终点的岩石）。

## 输入格式

第一行包含三个整数 $L,N,M$，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 $L \geq 1$ 且 $N \geq M \geq 0$。

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

## 输出格式

一个整数，即最短跳跃距离的最大值。

##输入输出样例#1

###输入#1

```
25 5 2 
2
11
14
17
21
```

###输出#1

```
4
```

## 说明/提示

### 输入输出样例 1 说明

将与起点距离为 2 和 14 的两个岩石移走后，最短的跳跃距离为 4（从与起点距离 17 的岩石跳到距离 21 的岩石，或者从距离 21 的岩石跳到终点）。

### 数据规模与约定

对于 $20\%$的数据，$0 \le M \le N \le 10$。    
对于 $50\%$ 的数据，$0 \le M \le N \le 100$。  
对于 $100\%$ 的数据，$0 \le M \le N \le 50000,1 \le L 
 \le 10^9$。

代码如下：
def main():
    import sys
    input = sys.stdin.read().split()
    L = int(input[0])   
    N = int(input[1])    
    M = int(input[2])    
    D = list(map(int, input[3:3+N]))  

    def is_possible(x):
        prev = 0  
        remove = 0  
        for d in D:
            if d - prev < x:
                remove += 1  
            else:
                prev = d 
        if L - prev < x:
            remove += 1
        return remove <= M

  
    left, right = 1, L
    ans = 0
    while left <= right:
        mid = (left + right) // 2
        if is_possible(mid):
            ans = mid 
            left = mid + 1 
        else:
            right = mid - 1  
    print(ans)

if __name__ == "__main__":
    main()

代码说明
对于is_possible(x)：
初始化prev=0（起点位置），remove=0（移走计数）。遍历每块岩石：若当前岩石与prev的距离<x，则移走（remove+1）；否则保留（prev更新）。最后检查最后一块保留岩石到终点的距离：若<x，需额外移走（remove+1）。返回remove≤M（是否可行
最后二分查找通过不断调整左右边界，找到最大的可行x