P10450 [USACO03MAR] Best Cow Fences G

· · 题解

思路：

简单题。

考虑二分答案 mid。

我们需要找到一个 l,r 使得：

\frac{\sum_{i=l}^r a_i}{r-l+1} \ge mid

转换得：

\sum_{i=l}^ r (a_i - mid) \ge 0

那么将序列中每个数减去 mid，然后相当于求一个长度大于等于 L 的最大子段和，判断一下是否大于 0 即可。

时间复杂度为 O(N \log W)。