自动搬运

查看原文

来自洛谷，原作者为

	Y_ATM_K ด้้้้้็้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็AFO!

搬运于2025-08-24 22:42:21，当前版本为作者最后更新于2022-11-16 22:16:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题面

分析

容易发现，青蛙从左跳到右和从右到左没有区别，因此相当于青蛙从左到右跳 $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;
}