M08210: 河中跳房子

binary search, greedy, http://cs101.openjudge.cn/pctbook/M08210

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

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

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

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

输入

第一行包含三个整数L, N, M，相邻两个整数之间用单个空格隔开。接下来N行，每行一个整数，表示每个岩石与起点的距离。岩石按与起点距离从近到远给出，且不会有两个岩石出现在同一个位置。

输出

一个整数，最长可能的最短跳跃距离。

样例输入

样例输出

提示

在移除位于2和14的两个岩石之后，最短跳跃距离为4（从17到21或从21到25）。

cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool canAchieve(const vector<int>& rocks, int L, int M, int minDist) {
    int removed = 0;  // 记录移除的岩石数量
    int prev = 0;     // 记录上一个岩石的位置（起点）

    for (int i = 1; i < rocks.size(); i++) {
        if (rocks[i] - rocks[prev] < minDist) {
            removed++;  // 如果当前岩石与上一个岩石的距离小于 minDist，则移除当前岩石
            if (removed > M) {
                return false;  // 超过可移除的岩石数量，返回 false
            }
        } else {
            prev = i;  // 更新上一个岩石的位置
        }
    }
    return true;  // 可以满足要求
}

int maxMinJump(int L, int N, int M, const vector<int>& rocks) {
    // 先将岩石位置排序，并加入起点和终点
    vector<int> allRocks = {0};
    allRocks.insert(allRocks.end(), rocks.begin(), rocks.end());
    allRocks.push_back(L);

    int left = 0, right = L + 1;  // 二分查找的范围是 [0, L+1)

    int ans = -1;
    while (left < right) {
        int mid = (left + right) / 2;  // 取中间偏右的值
        if (canAchieve(allRocks, L, M, mid)) {
            ans = mid;    // 如果 mid 可行，记录答案并尝试更大的值
            left = mid + 1;
        } else {
            right = mid;  // 否则尝试更小的值
        }
    }
    return ans;
}

int main() {
    int L, N, M;
    cin >> L >> N >> M;

    vector<int> rocks(N);
    for (int i = 0; i < N; i++) {
        cin >> rocks[i];
    }

    // 计算并输出答案
    cout << maxMinJump(L, N, M, rocks) << endl;

    return 0;
}

canAchieve 函数：
这个函数的作用是判断是否可以通过移除至多 M 个岩石，确保最短跳跃距离不小于 minDist。
从起点开始，依次检查岩石的位置。如果当前岩石与上一个岩石之间的距离小于 minDist，则认为这个岩石需要被移除。如果移除的岩石数超过了 M，则返回 false。否则，更新上一个岩石的位置。
maxMinJump 函数：
该函数使用二分查找来查找最大可能的最小跳跃距离。二分查找的范围是 [0, L+1)，每次计算中值 mid，并使用 canAchieve 判断是否可以通过移除岩石来实现该最小跳跃距离。如果可以，则更新答案，并尝试更大的 mid 值；否则，尝试更小的 mid 值。
main 函数：
从输入中读取参数 L（终点距离）、N（岩石数目）、M（最多可以移除的岩石数）以及岩石位置，最后调用 maxMinJump 函数计算并输出结果。
在 C++ 中，常常推荐使用常量引用（const T&）来传递对象，特别是当传递的是较大的数据结构（如 vector、string、map 等）时。这样既能提高性能，又能保证代码的清晰和安全。
复杂度分析：
时间复杂度：
二分查找的次数为 O(log L)。
每次检查是否可行的时间为 O(N)，因为我们要遍历岩石数组。
总的时间复杂度为 O(N * log L)。
空间复杂度：
主要使用一个数组 allRocks 来存储岩石位置和起点终点，空间复杂度为 O(N)。

M08210: 河中跳房子 ​

M08210: 河中跳房子