【题目描述】

每年奶牛们都要举办各种特殊版本的跳房子比赛，包括在河里从一个岩石跳到另一个岩石。这项激动人心的活动在一条长长的笔直河道中进行，在起点和离起点L远 (1 ≤ L≤ 1,000,000,000) 的终点处均有一个岩石。在起点和终点之间，有N (0 ≤ N ≤ 50,000) 个岩石，每个岩石与起点的距离分别为Di (0 < Di < L)。

在比赛过程中，奶牛轮流从起点出发，尝试到达终点，每一步只能从一个岩石跳到另一个岩石。当然，实力不济的奶牛是没有办法完成目标的。

农夫约翰为他的奶牛们感到自豪并且年年都观看了这项比赛。但随着时间的推移，看着其他农夫的胆小奶牛们在相距很近的岩石之间缓慢前行，他感到非常厌烦。他计划移走一些岩石，使得从起点到终点的过程中，最短的跳跃距离最长。他可以移走除起点和终点外的至多M (0 ≤ M ≤ N) 个岩石。

请帮助约翰确定移走这些岩石后，最长可能的最短跳跃距离是多少？

【输入描述】

第一行包含三个整数L, N, M，相邻两个整数之间用单个空格隔开。

接下来N行，每行一个整数，表示每个岩石与起点的距离。岩石按与起点距离从近到远给出，且不会有两个岩石出现在同一个位置。

【输出描述】

【样例输入】

25 5 2
2
11
14
17
21

【样例输出】

4

【题目分析】

这是一道 “二分+贪心”的典型例题

1. 问题转化成下面这样：

我们有一条长度为L的河道，起点在位置0，终点在位置L。河道中有N个岩石，位置分别是给定的。奶牛需要从起点跳到终点，每次跳跃必须从一个岩石跳到另一个岩石。农夫约翰可以移除最多M个岩石（不包括起点和终点），目标是使得在所有可能的跳跃方案中，最短的跳跃距离尽可能大。

换句话说，我们需要找到一个最大的最短跳跃距离D，使得在移除不超过M个岩石后，剩下的岩石（包括起点和终点）之间的所有相邻跳跃距离都不小于D。

2. 为什么是二分？

因为我们需要找到最大的D，使得在移除不超过M个岩石后，所有相邻跳跃距离≥D。这是一个典型的“最大化最小值”问题，通常可以用二分查找来解决。
二分查找的思路

（1）确定搜索范围：D的最小可能值是0（如果移除所有岩石，直接从起点跳到终点），最大可能值是L（起点到终点的距离）。
（2）二分查找：
    选择一个中间的D值（mid）。 
    检查是否可以移除不超过M个岩石，使得所有相邻跳跃距离≥mid。
    如果可以，说明D可以更大，所以调整左边界。
    如果不可以，说明D需要更小，所以调整右边界。
（3）终止条件：当左边界和右边界相遇时，找到最大的D。

3.如何验证D是否可行

编写一个函数isPossible(D)，判断是否可以移除不超过M个岩石，使得所有相邻跳跃距离≥D。具体步骤如下：
（1）初始化：
    prev = 0（起点位置）。
    count = 0（移除的岩石数量）。
（2）遍历所有岩石：
    对于每个岩石，计算它与prev的距离。
    如果距离 < D，说明需要移除该岩石（count++）。
    否则，保留该岩石，更新prev为当前岩石。
（3）检查终点：
    计算终点与最后一个保留的岩石的距离。
    如果距离 < D，可能需要移除更多岩石（但终点不能移除，所以可能需要调整）。
    返回count ≤ M。

4.例子

岩石位置：[2, 11, 14, 17, 21]，起点0，终点25，可以移除最多2个岩石。

二分查找过程：

1. 初始：left = 0，right = 25。

2. mid = 12：

• 起点0，第一个岩石2：距离2 < 12，移除2（count=1）。

• 下一个岩石11：距离11-0=11 < 12，移除11（count=2）。

• 下一个岩石14：距离14-0=14 ≥ 12，保留14（prev=14）。

• 下一个岩石17：距离17-14=3 < 12，移除17（count=3 > M=2）。

• 不可行。

• 验证isPossible(12)：

• 调整right = 11。

3. mid = 5：

• 起点0，岩石2：距离2 < 5，移除2（count=1）。

• 岩石11：距离11-0=11 ≥ 5，保留11（prev=11）。

• 岩石14：距离14-11=3 < 5，移除14（count=2）。

• 岩石17：距离17-11=6 ≥ 5，保留17（prev=17）。

• 岩石21：距离21-17=4 < 5，移除21（count=3 > M=2）。

• 不可行。

• 验证isPossible(5)：

• 调整right = 4。

4. mid = 2：

• 起点0，岩石2：距离2 ≥ 2，保留2（prev=2）。

• 岩石11：距离11-2=9 ≥ 2，保留11（prev=11）。

• 岩石14：距离14-11=3 ≥ 2，保留14（prev=14）。

• 岩石17：距离17-14=3 ≥ 2，保留17（prev=17）。

• 岩石21：距离21-17=4 ≥ 2，保留21（prev=21）。

• 终点25：距离25-21=4 ≥ 2。

• count=0 ≤ M=2。

• 可行。

• 验证isPossible(2)：

• 调整left = 3。

5. mid = 3：

• 起点0，岩石2：距离2 < 3，移除2（count=1）。

• 岩石11：距离11-0=11 ≥ 3，保留11（prev=11）。

• 岩石14：距离14-11=3 ≥ 3，保留14（prev=14）。

• 岩石17：距离17-14=3 ≥ 3，保留17（prev=17）。

• 岩石21：距离21-17=4 ≥ 3，保留21（prev=21）。

• 终点25：距离25-21=4 ≥ 3。

• count=1 ≤ M=2。

• 可行。

• 验证isPossible(3)：

• 调整left = 4。

6. mid = 4：

• 起点0，岩石2：距离2 < 4，移除2（count=1）。

• 岩石11：距离11-0=11 ≥ 4，保留11（prev=11）。

• 岩石14：距离14-11=3 < 4，移除14（count=2）。

• 岩石17：距离17-11=6 ≥ 4，保留17（prev=17）。

• 岩石21：距离21-17=4 ≥ 4，保留21（prev=21）。

• 终点25：距离25-21=4 ≥ 4。

• count=2 ≤ M=2。

• 可行。

• 验证isPossible(4)：

• 调整left = 5。

7. mid = 5：

• 之前验证过不可行。

• 调整right = 4。

8. 终止：left = 4，right = 4，输出4。

为什么输出是4？

因为在移除岩石2和14后，剩下的岩石是[11, 17, 21]，跳跃距离为：

• 0 → 11：11

• 11 → 17：6

• 17 → 21：4

• 21 → 25：4 最短跳跃距离是4，且移除的岩石数量是2 ≤ M=2。无法通过移除≤2个岩石得到更大的最短跳跃距离。

【参考答案】

#include<bits/stdc++.h>
using namespace std;
int rocks[100000];//假设岩石数量不超过 100000

// 判断是否可以通过移除最多 M 块岩石，使得最小跳跃距离至少为 D
bool isPossible(int D, int N, int L, int M) {
    int prev = 0; // 起点
    int count = 0;
    for (int i = 0; i < N; i++) {
        if (rocks[i] - prev < D) {
            count++; // 移除当前岩石
        } else {
            prev = rocks[i]; // 保留当前岩石
        }
        if (count > M) return false;
    }
    // 检查终点
    if (L - prev < D) {
        count++; // 需要移除最后一个岩石（但终点不能移除）
        if (count > M) return false;
    }
    return count <= M;
}

int main() {
    int L, N, M;
    cin>>L>>N>>M;
    for (int i = 0; i < N; i++) {
        cin>>rocks[i];
    }
    // 二分查找
    int left = 0, right = L;
    int ans = 0;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (isPossible(mid, N, L, M)) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
	cout<<ans;
    return 0;
}