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

· · 题解

题面

分析

容易发现，青蛙从左跳到右和从右到左没有区别，因此相当于青蛙从左到右跳 2x 次。

通过几个样例，可以发现这样一个规律：对于一个跳跃能力 y，青蛙能跳过河 2x 次，当且仅当对于每个长度为 y 的区间，这个区间内 h 的和都大于等于 2x。

证明一下。

先证明必要性。

假设青蛙能跳过 2x 次，对于一个长度为 y 的区间，因为青蛙无论怎么跳，都必须经过这个区间，所以这个区间所有 h 的和必定大于等于 2x。

再证明充分性。

我们让 2x 只青蛙一起跳。对于青蛙跳一次能到达的区间 [1,y]，这里显然可以跳 2x 只青蛙。那么考虑让 1 位置上的青蛙跳到 y+1 位置上。

若 h_1 \le h_{y+1}，则 1 的青蛙全部能跳到 y+1 上；

若 h_1 > h_{y+1}，因为 \sum_{i=2}^{y+1}h_i \ge 2x，

即 \sum_{i=2}^{y}h_i \ge 2x - h_{y+1}，所以区间 [2,y] 能容纳 2x - h_{y+1} 之青蛙，可以让多出来的几只跳到 [2,y] 中。

以此类推，可以让 2x 只青蛙全部跳过河。

于是可以用双指针扫一遍，得到满足条件的最小的 y 即可。

时间复杂度 O(n).

代码

#include <bits/stdc++.h>
#define N 100005
using namespace std;
int n,T,h[N],ans;
int main() {
    scanf("%d%d",&n,&T);T<<=1;
    for(int i=1;i<n;++i) scanf("%d",&h[i]);
    for(int i=1,j=0,sum=0;i<n;++i) {
        while(j<n&&sum<T) sum+=h[++j];
        ans=max(ans,j-i+1);
        sum-=h[i];
    }
    printf("%d\n",ans);
    return 0;
}