河中跳房子#自作聪明的约翰

解题思路:

步骤分析：

1.不移除任何岩石时，岩石之间的跳跃距离分别是：

最短跳跃距离是 3。

从起点到岩石 2：2

从岩石 2 到岩石 11：9

从岩石 11 到岩石 14：3

从岩石 14 到岩石 17：3

从岩石 17 到岩石 21：4

从岩石 21 到终点 25：4

2.移除岩石：假设我们移除岩石 11 和 14，这样剩下的岩石是 2, 17, 21。

最短跳跃距离是 4。

从起点到岩石 2：2

从岩石 2 到岩石 17：15

从岩石 17 到岩石 21：4

从岩石 21 到终点 25：4

3.尝试移除其他岩石：

如果我们移除岩石 2 和 14，最短跳跃距离也为 4。

4.所以，最长可能的最短跳跃距离是 4。

具体分析：

1.初始化：

len = 25, n = 5, m = 2

岩石位置 d[] = {0, 2, 11, 14, 17, 21}（假设起点位置为 0，终点位置为 25）

2.二分查找过程：

初始 l = 0, r = 25

计算 mid = (l + r + 1) / 2 = 13，调用 check(13)。

check(13) 的结果是 false，因为最短跳跃距离大于等于 13 时，需要移除超过 2 个岩石。

因此更新右边界 r = 12。

3.继续进行二分查找，直到得到最大可行的最短跳跃距离。

4.最终输出：

l 最终为 4，表示最长可能的最短跳跃距离是 4。

注意事项:
if (len - p < x) 

{ 

    // 如果从最后一个岩石到终点的跳跃距离小于x，则需要移除终点        

    ct++; // 移除终点    }

当我们遍历到最后一个岩石时，最后的跳跃（从最后一个岩石到终点）也需要满足最短跳跃距离 x。

如果从最后一个岩石到终点的距离小于 x，说明我们需要移除这个岩石，并且考虑一个新的“终点”。

参考代码:

#include <stdio.h>

#define N 50005  // 定义岩石数量的最大值

int len, n, m, d[N]; // len表示河道长度，n表示岩石的数量，m表示最多可移除的岩石数量，d数组存储每个岩石的距离

// 判断是否能移除M个点使得最短跳跃距离大于等于x
int check(int x) {
    int ct = 0, p = 0; // ct表示移除的岩石数量，p表示上一个选中的岩石的位置
    for (int i = 1; i <= n; ++i) {
        if (d[i] - p < x) { // 如果当前岩石到上一个岩石的跳跃距离小于x，则需要移除
            ct++;  // 移除当前岩石
        } else { // 如果跳跃距离大于等于x，则选择当前岩石
            p = d[i]; // 更新上一个岩石的位置
        }
    }
    if (len - p < x) { // 如果从最后一个岩石到终点的跳跃距离小于x，则需要移除终点
        ct++; // 移除终点
    }
    return ct <= m; // 如果移除的岩石数不超过最大移除数量m，返回真（表示可以满足条件）
}

int main() {
    scanf("%d %d %d", &len, &n, &m); // 输入河流长度len、岩石数量n和可移除岩石数量m
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &d[i]); // 输入每个岩石与起点的距离
    }

    int l = 0, r = len, mid; // l表示跳跃距离的最小值，r表示跳跃距离的最大值，mid是二分查找中的中值
    while (l < r) { // 二分查找最短跳跃距离
        mid = (l + r + 1) / 2; // 计算中间值，使用l + r + 1以确保可以向右移动
        if (check(mid)) { // 如果mid能够满足条件，即最短跳跃距离大于等于mid
            l = mid; // 调整最小值为mid，尝试更大的跳跃距离
        } else {
            r = mid - 1; // 如果mid不能满足条件，调整最大值为mid-1，尝试更小的跳跃距离
        }
    }
    
    printf("%d\n", l); // 输出最终结果，即最长可能的最短跳跃距离
    return 0; // 程序正常结束
}