问题描述

一年一度的"跳石头"比赛又要开始了！

这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 NN 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。

为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走MM 块岩石（不能移走起点和终点的岩石）。

输入描述

输入文件第一行包含三个整数 L，N，ML，N，M，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。

接下来 NN 行，每行一个整数，第 ii 行的整数 Di（0<Di<L）Di​（0<Di​<L）表示第 ii 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。

其中，0≤M≤N≤5×104，1≤L≤1090≤M≤N≤5×104，1≤L≤109。

更新：数据于 2024 年 10 月 15 日进行了加强。

输出描述

输出只包含一个整数，即最短跳跃距离的最大值。

输入输出样例

示例

输入

25 5 2
2
11
14
17
21

输出

4

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

总通过次数: 6066  |  总提交次数: 7352  |  通过率: 82.5%

难度: 困难   标签: 2015, 贪心, NOIP, 二分

算法思路：二分答案 + 贪心验证

​​核心思想​​：通过二分法枚举最短跳跃距离的最大值，用贪心策略验证该距离是否可行

1

算法步骤图解

        起点        岩石1       岩石2       岩石3       终点
0        |----------|-----------|-----------|-----------> L
距离：      d1         d2         d3         d4

二分目标：找到最大的 d，使得移除 ≤ M 块岩石后，所有 d_i ≥ d

C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool check(int d, int m, vector<int>& rocks, int L) {
    int prev = 0;       // 上一块保留岩石的位置（起点为0）
    int remove_count = 0; // 移除岩石计数
    
    for (int i = 0; i < rocks.size(); i++) {
        // 当前距离小于d时需要移除岩石
        if (rocks[i] - prev < d) {
            remove_count++;
            if (remove_count > m) return false; // 提前终止
        } else {
            prev = rocks[i]; // 保留当前岩石
        }
    }
    // 检查最后一段（最后岩石到终点）
    if (L - prev < d) remove_count++;
    
    return remove_count <= m;
}

int main() {
    int L, N, M;
    cin >> L >> N >> M;
    vector<int> rocks(N);
    for (int i = 0; i < N; i++) {
        cin >> rocks[i];
    }
    sort(rocks.begin(), rocks.end()); // 确保有序
    
    int left = 1;      // 最小跳跃距离
    int right = L;     // 最大跳跃距离
    int ans = 0;
    
    while (left <= right) {
        int mid = left + (right - left) / 2; // 避免溢出
        if (check(mid, M, rocks, L)) {
            ans = mid;       // 当前方案可行
            left = mid + 1;  // 尝试更大的距离
        } else {
            right = mid - 1; // 尝试更小的距离
        }
    }
    cout << ans << endl;
    return 0;
}

代码解析

1. check() 验证函数

bool check(int d, int m, vector<int>& rocks, int L) {
    int prev = 0;       // 起点位置
    int remove_count = 0;
    
    for (int pos : rocks) {
        if (pos - prev < d) { // 距离不足d
            remove_count++;    // 移除当前岩石
            if (remove_count > m) return false;
        } else {
            prev = pos; // 保留岩石并更新位置
        }
    }
    // 检查终点段距离
    if (L - prev < d) remove_count++; 
    
    return remove_count <= m;
}

• ​​贪心策略​​：从左向右扫描岩石，若当前岩石与前一块保留岩石的距离 < d 则移除
• ​​终点处理​​：单独检查最后一块岩石到终点的距离
• ​​提前终止​​：当移除数 > M 时立即返回 false

2. 二分查找框架

while (left <= right) {
    int mid = left + (right - left) / 2; // 防溢出
    if (check(mid, M, rocks, L)) {
        ans = mid;       // 记录可行解
        left = mid + 1;  // 尝试更大的d
    } else {
        right = mid - 1; // 尝试更小的d
    }
}

• ​​单调性​​：d 越大，需要移除的岩石越多
• ​​终止条件​​：left > right 时，ans 即为最大值

实例验证（样例输入）

输入：L=25, N=5, M=2, 岩石=[2, 11, 14, 17, 21]
验证 d=4：
  0→11 (移除2) →17 (移除14) →21→25
  最小距离：min(11-0, 17-11, 21-17, 25-21)=4
输出：4 ✓

关键测试点

测试类型	输入示例	验证要点
边界值	M=0	原始最小距离
极端情况	M=N	结果应为 L
密集分布	[1,2,3,..10], L=100	移除中间岩石
大跨度	L=1e9, N=5e4	性能测试

优化建议

1. ​​输入优化​​：

   ios::sync_with_stdio(false);
   cin.tie(0); // 加速IO

2. ​​检查函数优化​​：

   // 在循环内添加提前终止
   if (remove_count > m) return false;

3. ​​二分边界优化​​：

   right = *max_element(rocks.begin(), rocks.end()); // 缩小右边界

4. ​​终点处理优化​​：

   rocks.push_back(L); // 将终点加入岩石数组

复杂度分析

• ​​时间复杂度​​：O(N log L)
  • 二分：O(log L)
  • 检查：O(N)
• ​​空间复杂度​​：O(N)

注意事项

1. ​​终点处理​​：必须单独检查终点段距离（常见错误点）
2. ​​边界条件​​：当 M=N 时直接返回 L
3. ​​数据范围​​：L 最大 10⁹ 需用 int 即可
4. ​​有序保证​​：虽然题目说有序，实际可加 sort() 增强鲁棒性