AcWing 102. 最佳牛围栏
原题链接
简单
作者:
皓首不倦
,
2020-09-15 20:49:35
,
所有人可见
,
阅读 314
'''
二分枚举平均值的最大值
'''
N, F = map(int, input().split())
arr = [0] * N
max_val = -1
for i in range(N):
arr[i] = int(input())
max_val = max(max_val, arr[i])
def is_valid(mean_val):
S = [0] * N # 序列减去均值之后的新序列的前缀和
S[0] = arr[0] - mean_val
for i in range(1, N):
S[i] = S[i-1] + (arr[i] - mean_val)
if S[F-1] >= 0:
return True
min_s = 0 # 最小前缀和
i, j = 0, F
while j <= N-1:
min_s = min(min_s, S[i])
if S[j] - min_s >= 0:
return True
i, j = i+1, j+1
return False
l, r = 0, max_val
ans = None
while abs(l-r) >= 1e-9:
mid = l + (r-l) / 2
if is_valid(mid):
ans = mid
l = mid
else:
r = mid
ans *= 1000
if abs(int(ans + 0.5) - ans) <= 1e-5:
ans = int(ans + 0.5)
else:
ans = int(ans)
print(int(ans))