P8775 [蓝桥杯 2022 省 A] 青蛙过河 题解

xhgua · 2023-03-02 19:53:41 · 题解

题目链接：\texttt{Link}

有 n-1 块石头排成一条直线，第 i 块石头有一个高度 h_i，小青蛙打算经过河里的石头跳到对岸。

小青蛙每次跳跃必须落在一块石头或者岸上，每次从一块石头起跳，这块石头的高度就会下降 1，当石头的高度下降到 0 时小青蛙不能再跳到这块石头上（某次跳跃后使石头高度下降到 0 是允许的)。

小青蛙一共需要去学校上 x 天课，所以它需要往返 2x 次。当小青蛙具有一个跳跃能力 y 时，它能跳不超过 y 的距离。

请问小青蛙的跳跃能力至少是多少才能用这些石头上完 x 次课。

跳回来和跳到对岸是没有区别的，所以题目可以看作有 2x 只青蛙一起从左岸跳到右岸。

不难想到二分 y 的值，通过判断当前 y 是否能够使 2x 只青蛙跳过岸来缩小边界。

难点在于 check 函数上，如何判断某个跳跃能力是否能够使 2x 只青蛙跳过岸呢？

容易发现，任意一个长度为 y 的区间都会被每只青蛙踩至少一次，那么 2x 只青蛙就至少会踩 2x 次，所以每个区间内的高度和都必须要 \geq 2x。

在这 2x 只青蛙过河的任意时刻，每个区间的青蛙个数和不会超过 2x，所以满足上面的条件后一定可以使所有青蛙过河。

这样描述可能不是很好理解，我们来模拟一下青蛙跳跃的过程：

• 刚开始，所有青蛙都跳出一步，此时 2x 只青蛙均在区间 [1,y] 中。

• 紧接着，处于石头 1 上的所有青蛙跳到区间 [2,y+1] 中，由于每个区间的高度和都 \geq 2x，所以区间 [2,y+1] 一定能容下这些青蛙。

• 之后青蛙们就可以以类似的方式跳到 [3,y+2], [4,y+3],\dots 一直到 [n-y,n-1]，然后就可以一步到达对岸。

故每个区间高度和 \geq 2x 是 y 合法的充分必要条件。

有了这个性质之后，check 函数就很好写了，使用前缀和快速计算出每个区间的高度和即可。

#include <bits/stdc++.h>

#define i64 long long
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)

using namespace std;

const int N = 1e5 + 5;

int n, x;
i64 arr[N], sum[N];

bool check(int y) {
    rep(i, y, n - 1) if(sum[i] - sum[i - y] < 2 * x) return false;
    return true;
}

int main() {

    cin >> n >> x;
    rep(i, 1, n - 1) {
        cin >> arr[i];
        sum[i] = sum[i - 1] + arr[i];
    }

    int l = 1, r = n;
    while(l < r) {
        int mid = (l + r) / 2;

        if(check(mid)) r = mid;
        else l = mid + 1;
    }

    cout << r << endl;

    return 0;
}