轻功水上漂

FisherKK edited 2 年,11 月前

题面: 给定n个荷叶, 以及m个木桩, 和最远距离d, 使得每相邻两个木桩的最大值最小(将0和d也看做是一个桩)

水上漂是一道经典的最大值最小化最小值最大化问题, 这样的问题和二分搜索的思想是一样的。

二分搜索本质上是查找某个值x, 使得命题$C(x)$为真
而在这道题当中可以定义$C(x)$为相邻两个桩之间的最大距离不超过x, 那么我们只需要每次二分搜索距离就可以了,
其中很重要的一个部分在于如何判断$C(x)$为真, 可以这样认为, 对于莲叶$0, y_1, y_2, y_3, ...., y_i, y_{i+1},
… d$, 如果在$y_i$的位置上扎了桩, 那么就要下一个桩的位置$y_m$满足$y_m - y_i <= x$且$y_{m + 1} - y_i > x$(终点处可以额外考虑?), 如果不能找到说明这个距离x无法被满足。到最后如果无法到达终点说明x也无法被满足

再者对于二分的上界和下界, 上界ub保存能够使$C(x)$为真的距离,下界lb保存为假的距离

#include <iostream>
using namespace std;
const int MAXN = 100000 + 5;
int n, m, d; // n表示莲叶数量, m表示桩数量, d表示最远距离
int arr[MAXN];
void solve();
int main() {
    cin >> n >> m >> d;
    arr[0] = 0; int i; // 将起点0和终点d也看做是一个节点, 添加起点
    for (i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    arr[i] = d; // 添加终点
    solve();
}
bool C(int x) {
    /*
    判断是否可以用m个木桩使得任意两个桩之间的最大间距不超过d
    思路就是从0开始扎桩, 第一个桩应该扎在满足最远的第i个莲叶, 且莲叶和0的距离小于等于x
    以此类推, 更新桩的位置, 再次寻找满足上述要求的莲叶扎桩
    */
    int last = 0, crt = 0; // last记录当前木桩, crt记录当前莲叶位置
    for (int i = 0; i < m; i++) {
        crt = last + 1; // 从木桩的下一个位置开始迭代
        while (crt < n + 2 && arr[crt] - arr[last] <= x) {
            crt++; // 如果下一个位置和木桩的距离小于x, 就到后面一个位置, 直到和桩的距离大于x
        }
        if (crt == n + 2 && arr[n + 1] - arr[last] <= x) return true; // 判断如果已经到了终点, 直接返回可行
        if (crt == last + 1) return false; // 如果crt根本到不了下一步, 已经失败
        last = crt - 1; // 将crt的上一个位置扎桩
    }
    if (arr[n + 1] - arr[last] <= x) return true; // 如果所有的桩子都扎完了, 而且终点和最后一个桩的距离小于等于d的话, 可行
    return false; // 否则这个x就无法满足
}
void solve() { // 采用二分搜索的思想, 搜索最小的距离x, lb存储不能满足C(x)的下界, ub存储满足C(x)的上界
    int lb = 0, ub = d;
    while (ub - lb > 1) {
        int mid = (lb + ub) / 2;
        if (C(mid)) ub = mid; // 如果满足更新上界
        else lb = mid; // 如果不满足,更新下界
    }
    cout << ub << endl;
}

Comments