蓝桥杯 Java 青蛙过河

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改/**二分法从大（n）到小找足够小的步长前缀和记录每个位置的前面有的总石头数（一个石头表示可以容纳一个青蛙，一位置有多少个石头hi就是多少），方便计算相当于2x个青蛙从起点到终点起点0个石头，终点无数个石头，代表可以容纳无数个青蛙检查步长是否符合要求：对每个点检查如果这个点能跳到的区域内的石头数够2x（也就是下一步可以容纳2x个青蛙）（这一步用两个前缀和相减获得）如果当前点的可跳区域包含终点就相当于可以直接到终点，而前面肯定是算了可以到当前点的举例：按题目意思h就为0 1 0 1 0 INF前缀和就为0 1 1 2 2 INF如果步长为2那么先检查索引为0的点0 1 2 3 4 5可跳点为 1 2该区域总石头数为 1 - 0 = 1 < 2x也就是说青蛙如果在索引为0的点以当前步长能力无法跳到下一区域如果步长为4那么先检查索引为0的点0 1 2 3 4 5可跳点为 1 2 3 4该区域总石头数为 2 - 0 = 2 = 2x也就是说青蛙如果在索引为0的点以当前步长能力能跳到下一区域检查索引为1，该点可以直接跳到终点所以步长为4可以优化：前缀和不用考虑终点，终点直接利用长度判定即可
*/
public class Main {static int n,x;static int[] q;public static void main(String[] args) {Scanner scan = new Scanner(System.in);n = scan.nextInt();x = scan.nextInt();q = new int[n];for(int i = 1;i < n;i++)q[i] = scan.nextInt() + q[i-1];int l=0;int r=n;// 二分法提高寻找最小区间（步长k=l）的效率while(l < r) {//如果该步长符合要求——该步长内的所有连续区间承受的跳跃次数>2*x//则缩小kint mid = (l + r)/2;if(check(mid))r = mid;//反之，扩大kelsel = mid + 1;}//直到找到理论上最小就可以满足的步长K（==l）System.out.print(l);scan.close();}private static boolean check(int k) {//遍历所有步长为k的连续区间for(int i=0;i<n-k;i++)if(q[i+k]-q[i]<2*x)return false;return true;}
}