lanqiaoOJ 2097：青蛙过河 ← 二分+前缀和+贪心

【题目来源】
https://www.lanqiao.cn/problems/2097/learning/
https://www.luogu.com.cn/problem/P8775

【题目描述】
小青蛙住在一条河边，它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。

备注：此图由百度 AI 创作生成

河里的石头排成了一条直线，小青蛙每次跳跃必须落在一块石头或者岸上。不过，每块石头有一个高度，每次小青蛙从一块石头起跳，这块石头的高度就会下降 1，当石头的高度下降到 0 时小青蛙不能再跳到这块石头上（某次跳跃后使石头高度下降到 0 是允许的）。
小青蛙一共需要去学校上 x 天课，所以它需要往返 2x 次。当小青蛙具有一个跳跃能力 y 时，它能跳不超过 y 的距离。
请问小青蛙的跳跃能力至少是多少才能用这些石头上完 x 次课。

【输入格式】
输入的第一行包含两个整数 n，x，分别表示河的宽度和小青蛙需要去学校的天数。请注意 2x 才是实际过河的次数。
第二行包含 n-1 个非负整数 ，其中 Hi>0 表示在河中与小青蛙的家相距 i 的地方有一块高度为 Hi 的石头，Hi=0 表示这个位置没有石头。

【输出格式】
输出一行，包含一个整数，表示小青蛙需要的最低跳跃能力。

【输入样例】
5 1
1 0 1 0

【输出样例】
4

【样例说明】
由于只有两块高度为 1 的石头，所以往返只能各用一块。第 1 块石头和对岸的距离为 4，如果小青蛙的跳跃能力为 3 则无法满足要求。所以小青蛙最少需要 4 的跳跃能力。

【评测用例规模与约定】
对于 30% 的评测用例，n≤100；
对于 60% 的评测用例，n≤1000；
对于所有评测用例，1≤n≤10^5，1≤x≤10^9，1≤Hi≤10^4。

【算法分析】
● 本题中，整数 n，x 分别表示河的宽度和小青蛙需要去学校的天数。由于 n 和 x 的值较大，所以需要使用二分与前缀和进行优化。
● 当数据比较大时，可能会产生溢出。所以，本题中可以使用 mid=le+(ri-le)/2 而不是 mid=(le+ri)/2。
● 每一次去学校，都要过两次河，所以实际上青蛙过河的总次数为 2x。
● 由题意易得，要想使青蛙成功地过 2x 次河，就要使每一个长度为 y 的区间里的所有石块的高度和大于等于 2x。

【算法代码】

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;
int a[maxn];
int s[maxn];
int n,x;

bool check(int t) {
    for(int i=1; i<n-t+1; i++) {
        if(s[i+t-1]-s[i-1]<2*x) return false;
    }
    return true;
}

int main() {
    cin>>n>>x;
    for(int i=1; i<n; i++) {
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }

    int le=1, ri=n;
    while(le!=ri) {
        if(check((le+ri)/2)) ri=(le+ri)/2;
        else le=(le+ri)/2+1;
    }
    cout<<le;

    return 0;
}


/*
in:
5 1
1 0 1 0

out:
4
*/

【参考文献】
https://www.lanqiao.cn/problems/2097/learning/
https://www.luogu.com.cn/problem/solution/P8775