蓝桥杯链接
首先马上可以想到二分,难的是check函数
首先想一个必要条件,如果check(y)返回True,那么对于所有以i开始长度为y的区间,区间中所有数之和必然不少于2x
可以想象,因为最多跨y个长度,因此来回肯定都要经过这个区间,这个区间肯定要能被踩至少2x次
这个条件也是充分条件,因为如果所有长度为y的区间都能至少踩2x次,那么肯定能够完成2x次来回。
import sys; readline = sys.stdin.readline
read = lambda: [int(x) for x in readline().split()]
alloc = lambda *s: len(s) != 1 and [alloc(*s[1:]) for i in range(int(s[0]) + 2)] or [0] * int(s[0] + 2)
n, x = read()
n -= 1
arr = [0] + read()
s = [0] * (n + 1)
for i in range(1, n + 1): s[i] = s[i - 1] + arr[i]
check = lambda y : all(s[i] - s[i - y] >= 2 * x for i in range(y, n + 1))
l = 0; r = n + 1
while l < r:
mid = l + r >> 1
if check(mid): r = mid
else: l = mid + 1
print(l)