青蛙过河 - 蓝桥云课 (lanqiao.cn)

我们来分析一下，给个证明

假如河的宽度为5

0 ，1，2，3，4，5

我们会发现，按照题目0与5号位置是两岸，石头们则在1到4这四个位置。

我们要找到青蛙最小的跳跃范围来使得它能来回总共2n次。

我们想一想，小青蛙跳跃会有极限，它可以在极限内随意跳跃多大的距离，在理想情况下，小青蛙在可以分配的区间内尽可能的均衡跳跃，比如跳跃极限为2第一次在1，2这两块石头中选取1号跳跃，再一次跳到一号和二号时候，选择二号，这样实际上如果某一块石头率先被踩到0，那位之后一直选择2号（当跳跃到1，2号区间时候）。由此我们得出一个结论，就是使得1，2号这个区间的可以被踩得次数大于2n（因为青蛙往返总共2n次)，同理青蛙可以先跳到1，在从2，3选一块跳跃，这也就要求我们2，3这个区间的承载总次数也大于2n，由此我们就有了check来检查二分答案的依据了。

import java.awt.PageAttributes.OriginType;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.math.MathContext;
import java.security.PublicKey;
import java.sql.SQLIntegrityConstraintViolationException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.TreeMap;
import java.util.TreeSet;import javax.management.relation.InvalidRelationTypeException;
public class Main {	public static void main(String[] args) throws NumberFormatException, IOException  {
Scanner sc=new Scanner(System.in);
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw1=new PrintWriter(System.out);
String[] aStrings=br.readLine().split(" ");bb=Integer.parseInt(aStrings[0]);cc=Integer.parseInt(aStrings[1]);aa=new long[bb+3];pre=new long[bb+3];String[] bStrings=br.readLine().split(" ");int a;for(a=1;a<bb;a++) {aa[a]=Long.parseLong(bStrings[a-1]);pre[a]=pre[a-1]+aa[a];//前缀和便于记录一个区间的可承载数量的总数}pre[bb]=Long.MAX_VALUE;//为什么bb设为无穷大，大家想一下，根据样例如果我们跳到了3号，可以最大跳跃两个格子，那么我们肯定直接跳跃两个格子直接到对岸上去，也就是说到了最后一跃，我们不需要考虑最后一个区间的承载范围，索性将pre【bb】蛇为无穷大，肯定不会卡死在这里。要不然h会卡数据。int start=0;int end=bb;int answer=0;while(start<=end) {int mid=(start+end)>>>1;if(check(mid)==1) {answer=mid;//二分，答案合适，保存，缩小范围end=mid-1;}else {start=mid+1;}}System.out.println(answer);}public static long[] aa;public static long[] pre;public static int bb;public static int cc;public static int check(int a) {int b;for(b=0;b<=bb-a;b++) {long c=pre[b+a]-pre[b];//从对岸起，每次跳跃a个格子，判断承载力if(c<2*cc) {return 0;}}return 1;}
}