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
//则缩小k
int mid = (l + r)/2;
if(check(mid))
r = mid;
//反之,扩大k
else
l = 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;
}
}