第十三届蓝桥杯省赛A组题解传送门

题目大意

小青蛙要去学校，学校在河对岸
河的宽度是$n$，中间有等距离的$n-1$个石头，第$i$个石头的高度是$h_i$
小青蛙需要在家和学校间往返$x$次
小青蛙的跳跃能力是$y$时，它能跳不超过$y$的距离
小青蛙每次从一块石头上起跳，这块石头的高度就会减一
当一块石头的高度降为$0$后，小青蛙将再也无法站在这块石头上
问小青蛙的跳跃能力最小是多少才能用这些石头在家和学校间往返$2x$次

解题思路

往返$x$次可以等价于单向去学校$2x$次，便于理解
小青蛙的跳跃能力对能否过河$2x$次具有两段性，因此可以想到二分答案
那么每次$check$要判定当小青蛙的跳跃能力为$jump$时，能否过河$2x$次
最容易想到的一种$check$方法是贪心+模拟，每次跳跃都尽量跳到能跳到的最远
但这种写法如果在找最远距离时用笨方法循环会很慢，需要用并查集优化
另一种$check$思想是检查是否存在一个长度为$jump$的区间的石头高度和小于$2x$
如果存在，$return\ false$，否则$return\ true$
简单证明：
如果不存在一个长度为$jump$的区间的石头高度和小于$2x$
那么无论青蛙当前在哪块石头上，设青蛙在第$i$块石头上(可以把青蛙的家想成第$0$块石头，高度为$0$)，青蛙下一次跳跃都有落脚点(青蛙下一次跳跃的落脚点的范围是$i+1$到$i+jump$)
相反地，如果存在这样一个区间，那么某一状态这段区间的高度和会变成$0$，就是说这段区间整个废了，但是小青蛙无法一次性跳过这个废掉的区间

具体代码

#include <bits/stdc++.h>
typedef long long LL;
const int N = 1e5 + 10;
const int INF = 1e9 + 10;
int h[N];
LL s[N];
int n, x;
bool check(int jump)
{
    for (int i = 1; i + jump - 1 <= n - 1; ++i)
        if (s[i + jump - 1] - s[i - 1] < x)
            return false;
    return true;
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin >> n >> x;
    x <<= 1;
    for (int i = 1; i <= n - 1; ++i)
    {
        std::cin >> h[i];
        s[i] = s[i - 1] + h[i];
    }
    int l = 1, r = n;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    std::cout << l << '\n';
    return 0;
}