算法1

二分法 + 前缀和

在0到2000之前, 用二分法猜一个平均值.
然后所有的序列元素都减去这个平均值, 然后求前缀和, 观察一下长度至少为F的序列里面, 有没有和大于等于0的.
求长度至少为F的序列的和的方法: 前缀和 - 前缀和F阶滞后项的最小值

最容易出bug的地方, 最后返回的应该是r, 如果返回l, 那么, 可能精度出问题.
题目要求是求下整, 所以, 选择更大的r是最佳选择.
比如, 正确的答案是6500, 而l可能为6499.9998, 而r可能为6500.0002, 对r进行下整才能够得到正确答案6500.

时间复杂度

O(N * log(M)), M <= 2000, 表示最大平均值的范围为0到2000之间.

参考文献

<算法竞赛进阶指南>

Python 代码

def check(mid):
    s = 0
    S = [0]
    M = float("inf")
    for i, e in enumerate(L, 1):
        e -= mid
        s += e
        S.append(s)
        if i >= F:
            M = min(M, S[i - F])
            if s - M > 1e-6: return True
    return False

N, F = map(int, input().split())
L = []
for _ in range(N):
    L.append(1000 * int(input()))
#print(L)

l, r = 0, max(L)
while r - l > 1e-3:
    mid = (l + r) / 2
    if check(mid):
        l = mid
    else:
        r = mid
print(int(r))