NOI1.11-10河中跳房子（NOIP2015跳石头）
6304+
作者：crxis 发布：2017-10-06 分类：二分
题目大意：n块石头排成一行，你至多可以取走k块，最终相邻两块石头之间的距离最小值最大是多少？
题目描述
一年一度的“跳石头”比赛又要开始了！这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有N块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走M块岩石（不能移走起点和终点的岩石）。
输入
第一行包含三个整数L, N, M，相邻两个整数之间用单个空格隔开。
接下来N行，每行一个整数，表示每个岩石与起点的距离。岩石按与起点距离从近到远给出，且不会有两个岩石出现在同一个位置。
输出
一个整数，最长可能的最短跳跃距离。
样例输入
25 5 2
2
11
14
17
21
样例输出
4
提示
NOIP2016提高组第二天第一题
解题思路
题目的答案范围已知，而且范围很大，对于每个答案可以快速验证是否可行，可以采用二分答案的方法。最短距离最大，其实就是越大越好——在二分的时候，如果中间值可行，继续猜后一半，而不是前一半，因为后一半可能有更好的！对于一个答案m，如果可行，那么相邻石头之间的距离都不小于m，也就是如果出现小于m的，那个石头必须移走。写一个函数判断当前答案需要移走多少块石头，如果不超过k块，那就可以，否则不行。
对于二分的结束条件，写法很多种，只要考虑周到就可以。
程序实现
