复赛四：跳石头

洛谷：P2678
OJ: I4953

问题分析：

  • 给定起点和终点，以及它们之间的 N 块岩石，选手必须从起点跳到终点，每次只能跳到相邻的岩石。
  • 组委会想要移除最多 M 块岩石，使得选手在比赛过程中最短的跳跃距离尽可能长。
  • 我们需要找到移除岩石的方案，使得最短的跳跃距离最大化。

解决方案：

  • 二分查找：
    • 我们可以将最短跳跃距离视为一个搜索空间的变量 D，范围从 0 到 L。
    • 通过二分查找的方法，我们尝试不同的 D，检查在给定的 D 下，是否可以通过移除不超过 M 个岩石，使得所有相邻岩石之间的距离都大于等于 D。
    • 如果在某个 D 下可行，我们尝试更大的 D；如果不可行，我们尝试更小的 D。
  • 可行性检查函数 isPossible：
    • 遍历所有的岩石位置，计算每一跳的距离。
    • 如果当前岩石与上一个未被移除的岩石之间的距离小于 D，则需要移除当前岩石，计数器 cnt 加一。
    • 如果 cnt 超过了 M，则在当前的 D 下不可行，返回 false。
    • 如果遍历完成且 cnt 不超过 M，说明在当前的 D 下可行，返回 true。

代码实现：

 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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/**************************************************************** 
 * Description: 2015_S_semi_4   跳石头
 * Author: Alex Li
 * Date: 2024-09-19 19:46:20
 * LastEditTime: 2024-09-19 20:25:01
****************************************************************/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 检查在最小跳跃距离为 D 的情况下，是否可以通过移除不超过 M 个岩石，从起点跳到终点
bool isPossible(const vector<int>& positions, int N, int M, int D) {
    int cnt = 0;          // 已移除的岩石数量
    int prev = 0;         // 上一个未被移除的岩石在 positions 中的索引，初始为起点
    int size = positions.size(); // 岩石总数（包括起点和终点）

    // 遍历所有岩石，从起点开始
    for (int i = 1; i < size; ++i) {
        // 计算当前岩石与上一个未被移除的岩石之间的距离
        int distance = positions[i] - positions[prev];
        if (distance < D) {
            // 如果距离小于最小跳跃距离 D，需要移除当前岩石
            cnt++;
            if (cnt > M) {
                // 如果移除的岩石数量超过允许的最大值 M，则无法实现，返回 false
                return false;
            }
            // 当前岩石被移除，prev 不变，继续检查下一块岩石
        } else {
            // 如果距离大于等于 D，更新 prev 为当前岩石的索引
            prev = i;
        }
    }
    // 遍历完成且移除的岩石数量不超过 M，返回 true
    return true;
}

int main() {
    int L, N, M;
    cin >> L >> N >> M;   // 读取起点到终点的距离 L，岩石数量 N，最多可移除的岩石数 M
    vector<int> positions(N + 2); // 创建一个大小为 N+2 的向量，包含起点和终点
    positions[0] = 0;     // 起点位置为 0
    for (int i = 1; i <= N; ++i) {
        cin >> positions[i]; // 读取第 i 块岩石的位置
    }
    positions[N + 1] = L; // 终点位置为 L
    sort(positions.begin(), positions.end()); // 对所有岩石位置进行排序

    int low = 0;          // 二分查找的下界，最小可能的最小跳跃距离
    int high = L;         // 二分查找的上界，最大可能的最小跳跃距离

    // 开始二分查找，寻找最大化的最小跳跃距离
    while (low < high) {
        // 取中间值，向上取整，避免无限循环
        int mid = (low + high + 1) / 2;
        // 检查在最小跳跃距离为 mid 的情况下，是否可行
        if (isPossible(positions, N, M, mid)) {
            // 如果可行，说明可以尝试更大的最小跳跃距离，更新 low
            low = mid;
        } else {
            // 如果不可行，说明最小跳跃距离过大，更新 high
            high = mid - 1;
        }
    }
    // 输出最大化的最小跳跃距离
    cout << low << endl;
    return 0;
}
Previous Topic
Back to Lesson
Next Quiz