奶牛跳格子问题题解

一、题目分析

题目要求通过移除最多M块石头，最大化奶牛跳跃的最小距离。关键条件：

1. 起点和终点石头不能移除，中间有N块石头；
2. 目标是找到移除M块石头后，所有相邻石头间距离的最小值的最大值。

二、算法思路

1. 二分查找：

   • 二分可能的最小跳跃距离mid，判断是否可以通过移除最多M块石头，使所有相邻距离≥mid；
   • 若可以，尝试更大的mid；否则，尝试更小的mid。

2. 贪心验证：

   • 从起点开始，依次检查每段距离是否≥mid；
   • 若距离<mid，则移除当前石头（计数+1），否则保留并更新当前位置。

三、代码实现

#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;

int ans, n, m, l, w[50005];  // w数组存储石头位置，包括起点和终点

// 二分查找函数：寻找最大的最小跳跃距离
void erfen(int l, int r) {
    if (l > r) return;
    int mid = (l + r) / 2;
    int tmp = 0, s = 0, flag = 0;  // tmp:当前段距离，s:移除石头数，flag:是否可行
    
    for (int i = 1; i <= n + 1; i++) {
        tmp += w[i] - w[i - 1];  // 计算当前段距离
        if (tmp < mid && i == n + 1) { flag = 1; break; }  // 最后一段不足mid
        if (tmp < mid) s++;  // 距离不足，需移除石头
        else tmp = 0;  // 距离足够，重置当前段
        
        if (s > m) { flag = 1; break; }  // 移除石头数超过限制
    }
    
    if (!flag) {  // 可行：尝试更大的mid
        ans = max(ans, mid);
        erfen(mid + 1, r);
    } else {  // 不可行：尝试更小的mid
        erfen(l, mid - 1);
    }
}

int main() {
    scanf("%d%d%d", &l, &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
    sort(w + 1, w + 1 + n);  // 排序石头位置
    w[n + 1] = l;  // 添加终点
    
    ans = 1;  // 初始最小距离为1
    erfen(1, l);  // 二分查找范围[1, l]
    printf("%d\n", ans);
    return 0;
}

四、代码解释

1. 输入处理：

   • 读取河流长度L、石头数N、最多移除数M；
   • 读取中间石头位置并排序，添加终点位置到数组末尾。

2. 二分查找：

   • 初始二分范围为[1, L]，ans记录当前最大最小距离；
   • 每次取mid=(l+r)/2，验证是否可通过移除≤M块石头使所有距离≥mid。

3. 贪心验证：

   • 遍历石头位置，计算相邻距离：
     • 若距离<mid，移除当前石头（s++）；
     • 若s>M，说明mid太大，标记为不可行；
     • 否则，更新ans并尝试更大的mid。

五、示例解析

输入：

25 5 2  
2 14 11 21 17  

1. 排序后石头位置：0（起点）、2、11、14、17、21、25（终点）；
2. 二分过程：
   • mid=4时，验证：
     • 0→2（2<4，移除2，s=1）；
     • 0→11（11≥4，tmp=0）；
     • 11→14（3<4，移除14，s=2）；
     • 11→17（6≥4，tmp=0）；
     • 17→21（4≥4，tmp=0）；
     • 21→25（4≥4，tmp=0）；
     • s=2≤M=2，可行，ans=4，尝试更大mid。
3. 输出：4

六、复杂度分析

• 时间复杂度：O(N log L)，其中N为石头数，L为河流长度；
  • 排序：O(N log N)；
  • 二分查找：O(log L)，每次验证：O(N)。
• 空间复杂度：O(N)，存储石头位置。

七、关键技巧

1. 二分答案：将最大化最小值问题转化为可行性判断问题；
2. 贪心验证：按顺序移除石头，确保每一步选择最优；
3. 边界处理：添加起点和终点，统一处理所有石头间距。