1.青蛙过河

1.题目描述

小青蛙住在一条河边, 它想到河对岸的学校去学习。小青蛙打算经过河里 的石头跳到对岸。

河里的石头排成了一条直线, 小青蛙每次跳跃必须落在一块石头或者岸上。 不过, 每块石头有一个高度, 每次小青蛙从一块石头起跳, 这块石头的高度就 会下降 1 , 当石头的高度下降到 0 时小青蛙不能再跳到这块石头上（某次跳跃 后使石头高度下降到 0 是允许的）。

小青蛙一共需要去学校上 天课, 所以它需要往返 次。当小青蛙具有 一个跳跃能力 时, 它能跳不超过 的距离。

请问小青蛙的跳跃能力至少是多少才能用这些石头上完 次课。

2.输入格式

输入的第一行包含两个整数 , 分别表示河的宽度和小青蛙需要去学校 的天数。请注意 才是实际过河的次数。
第二行包含 个非负整数 , 其中 表 示在河中与 小青蛙的家相距 的地方有一块高度为 ​的石头,
表示这个位置没有石头。

3.输出格式

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

4.样例输入

5 1
1 0 1 0

5.样例输出

4

6.数据范围

7.原题链接

青蛙过河

2.解题思路

假设青蛙可以按照某条路线从家跳往对岸，路线上所有的石子高度均减1，这个操作等价于“青蛙从对岸按照路线反向跳回家，路线上所有的石子高度均减1”。

这也说明，判断小青蛙能否往返次，等价于判断小青蛙能否从左往右跳重复次。

由题目可以发现，设小青蛙的跳跃能力为，当小青蛙跳跃能力越大，越容易满足“重复2x次”的约束，即求解的存在单调性：

• 当越大时，小青蛙每次可以跳的范围更大，可以跳更少的步数到达对岸，即更容易重复次，当时，无需经过任何石子就可以跳到对岸。
• 当越小时，小青蛙需要使用更多的步数才能到达对岸，更不容易满足“重复次”的约束。

本题最终需要求解的是：恰好满足约束的最小的 答案存在单调性，显然可以用二分答案的算法进行求解，初始区间：

1. 求出区间的中点，
2. 判断当小青蛙跳跃能力等于时，能否从左往右跳重复次
   1. 如果可以，则更新，调整搜索区间为（求最小值，因此调整右端点）
   2. 否则，调整搜索区间为
3. 如果，终止循环，否则回到

二分答案将求解最值问题转换成判定性问题，问题转变成当跳跃能力等于时，判断小青蛙能否从左往右跳次。

小青蛙最开始位于0处，跳跃能力等于，需要重复跳跃次，则首先要求从的石子高度必须大于等于，不然小青蛙迈出的第一步都无法重复次。

这个结论可以推广——“所有长度为的区间中石子高度之和必须大于等于”。

1. 如果所有长度为的区间中，石子高度之和等于则存在，则只要保证第一步在中选择一个可以跳跃的石子，则后续跳跃只需从当前位置跳到即可。这样可以保证重复次；
2. 如果所有长度为的区间中，石子高度之和大于：**则可以考虑去除某些石子的高度，从而构造出情况1，此时也是可以保证重复次的；
3. 如果可以重复跳跃次，所有区间长度为的区间中石子高度之和大于等于：对于任意区间，每次跳跃必须在区间中落脚。利用反证法，如果不在区间中落脚，等价于从的左边跳到了的右边，此时跳跃长度超过了能力上限，因此不合法。也就是说，每次跳跃对于任意长度等于的区间都落脚1次，重复次则说明该区间石子之和大于等于。

通过上面三点可以证明：“当跳跃能力等于时重复次”等价于“所有区间长度等于的区间石子高度之和大于等于”，利用这个结论进行二分答案的判定即可。

实现过程中事先预处理前缀和，从而可以求解区间和，时间复杂度。

实际上使用双指针，维护区间和始终大于 ，得到的最小区间长度则是答案，这样可做到 的复杂度。

Ac_code

1.C++

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
#define pb(s) push_back(s);
#define SZ(s) ((int)s.size());
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 200010;

LL n, x;
void solve()
{
	cin >> n >> x;
	std::vector<LL> s(n + 1);
	for (int i = 1; i < n; ++i) {
		cin >> s[i];
		s[i] += s[i - 1];
	}
	//最后一块石头，也就是终点，可以无限跳
	s[n] = 1e18;
	int l = 1, r = n;
	auto check = [&](int g) {
		for (int i = 0; i + g <= n; ++i) {
			int r = i + g;
			if (s[r] - s[i] < 2 * x) return false;
		}
		return true;
	};
	while (l < r) {
		int mid = l + r  >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}
	cout << r << '\n';
}
int main()
{
	ios_base :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t = 1;
	while (t--)
	{
		solve();
	}
	return 0;
}

2.Java

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        long x=sc.nextLong();
        long []arr=new long[n+1];
        for (int i=1;i<n;i++){
            arr[i]=sc.nextLong()+arr[i-1];
        }
        arr[n]=100000000000L;
        int l=0;
        int ans=0;
        for (int r=1;r<=n;r++){
            if (arr[r]-arr[l]>= 2*x){
                ans=Math.max(ans,r-l);
                l+=1;
            }
        }
        System.out.println(ans);
    }
}