这是一道很好玩的题。

题目描述

这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 $N$ 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 $M$ 块岩石（不能移走起点和终点的岩石）。

输入格式

第一行包含三个整数 L​，N，M，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 L ≥ 1 且 N ≥ M ≥ 0。接下来 N 行，每行一个整数，第 i 行的整数 Di (0 < Di < L)， 表示第 i 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。

输出格式

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

样例

输入

1
2
3
4
5
6
25 5 2 
2
11
14
17 
21

输出

1
4

算法描述

这道题，暴力枚举肯定能解决，但加上了最大移动石块数使得种类特别多，暴力枚举运行时间会很长。所以这道题还是需要进行算法优化的。

这道题我们使用二分搜索。

找到一个距离 mid​ ，从头开始跳石头。如果跳跃距离小于 mid​ ，说明当前距离不是最小值。那我们要移动石头，直到找到大于 mid​ 的距离。如果这个时候移动石头数小于要求数，那么我们选定的距离是当前情况下跳跃距离最小值中的最大值。如果移动石头数超过了要求数，说明在满足移动石头的条件下，当前情况有更小的距离。那么我们选择的 ​mid 就并不是最小值了。我们选择二分法来逼近。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
using namespace std;

bool judge(int x, int num_rocks, int num_move, int arr[])
{
    int cnt=0, now=0;
    
    for(int i=1; i<num_rocks+1; i++)
    {
        if(arr[i] - arr[now] < x)
            cnt++;
        else
            now = i;
    }
    
    if(cnt <= num_move)
        return true;
    return false;
}

int main()
{
    int distance, num_rocks, num_move;
    cin >> distance >> num_rocks >> num_move;
    
    int arr[num_rocks+2];	// +2 是为了记录起点和终点
    arr[0] = 0;
    arr[num_rocks+1] = distance;
  	// 读入数据
    for(int i=1; i<=num_rocks; i++)
        cin >> arr[i];
    
    int l = 1, r = distance;
    int res;
    while (l <= r)
    {
        int mid = (l + r) / 2;
      	// 判断mid是不是当前l，r情况下跳跃距离最小值的最大值
        if(judge(mid, num_rocks, num_move, arr))
        {
            // 记录答案
          	res = mid;
          	// 往下找
            l = mid + 1;
        }
        else	// 不是的话往前找
            r = mid - 1;
    }
    cout << res << endl;
    
    return 0;
}