这道题可以简化成:
给定一个正整数序列,求长度不小于F并且平均值最大的子段
接下来,我们先把一切条件去掉,完成这个问题——
给定x,判定一个子段的平均值是否至少为x
这就很简单,一种最简单的方法就是把序列中的每个数加起来再除以元素个数就可以做到。
我们再想想,现在我们的公式是(kl+kl+1+…+kr)/(r-l+1)>=x,如何把它简化呢?
只要把r-l+1移到右边,在根据两边都乘上一个r-l+1把x移到左边就可得到(kl-x)+(kl+1 - x)+…+(kr-x)>=0
所以,我们会把每个数减去x,存进一个b数组。
接下来,我们给定一个数组,问题就变成了——
给定x,判定是否存在平均值至少为x的子段
最容易想到的方法找出所有子段,也就是枚举所有左右端点,但这种方法用前缀和优化后的时间复杂度也是O(n^2),一定会超时。所以,我们要对这个方法进行改进。
经过思考,我们可以得到2种写法
1. 先用最大子段和模型求出最大子段和,如果最大子段和不小于x则有解,否则没有。
- O(n^2)的算法是通过前缀和优化,公式为sum[r]-sum[l-1]。这时,最好的方法是把2重循环变成1重循环。这里我们选择去掉枚举左端点来优化。但是,我们还是要求区间和呀。这时,我们从减法的角度想一想,要使差最小,被减数尽可能要大,减数要尽可能小。被减数已经确定了,所以我们从减数下手。实际上,我们只要让l-1的区间尽可能小,所得到的数就会尽可能大。
相当于我们在前缀和上再跑一个前缀最小值。