1. 2026: [蓝桥杯2022初赛] 青蛙过河

传送门：http://oj.ecustacm.cn/problem.php?id=2026

1.1. 题意

小青蛙住在一条河边，它想到河对岸的学校去学习。小青蛙打算经过河里 的石头跳到对岸。河里的石头排成了一条直线，小青蛙每次跳跃必须落在一块石头或者岸上。不过，每块石头有一个高度，每次小青蛙从一块石头起跳，这块石头的高度就会下降$1$，当石头的高度下降到$0$时小青蛙不能再跳到这块石头上（某次跳跃后使石头高度下降到$0$ 是允许的）。

小青蛙一共需要去学校上$x$天课，所以它需要往返$2x$次。当小青蛙具有一个跳跃能力$y$时，它能跳不超过$y$的距离。请问小青蛙的跳跃能力至少是多少才能用这些石头上完$x$次课。

1.2. Tag

二分答案、贪心

1.3. 难度

☆☆☆☆

1.4. 思路

往返累计$2x$次相当于单向走$2x$次。跳跃能力越大，越能保证可以通过$2x$次。因此可以使用二分答案，找到一个最小的满足条件的跳跃能力。

假设跳跃能力为$mid$，一种思想是每次能跳多远跳多远，然后去模拟判断$mid$是否合法，做法比较复杂，暂不展开。

另一种想法是判断每个长度为$mid$的区间之和是否大于等于$2x$，如果每个区间和都大于$2x$，肯定可以保证构造出一组解通过$2x$次。反过来是否成立可以自行思考一下。参考：https://www.zhihu.com/question/525176453/answer/2433729894

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
template <typename T>
inline T read(T& x) {
  x = 0;
  T w = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + (ch - '0');
    ch = getchar();
  }
  return x * w;
}
int h[maxn], sum[maxn];
int n, x;
//判断所有长度为mid的区间之和是否大于等于2x
bool check(int mid){
    for(int i = 1; i + mid - 1 <= n; i++)
        if(sum[i + mid - 1] - sum[i - 1] < 2 * x)return false;
    return true;
}
int main(){
    read(n); read(x);
    for(int i = 1; i <= n - 1; i++)//预处理前缀和
        read(h[i]), sum[i] = sum[i - 1] + h[i];
    sum[n] = 1e9 + 7;
    int left = 1, right = n, ans = n;
    while(left <= right)//二分答案
    {
        int mid = (left + right) >> 1;
        if(check(mid))
            ans = mid, right = mid - 1;//求最小合法解
        else
            left = mid + 1;
    }
    cout<<ans<<endl;
    return 0;
}