$\color{red}题目链接$

题目分析

可以用二分+前缀和解决。

首先,我们可以发现,

随着 $X$ 的增大,满足长度不小于 $F$ 且平均值不小于 $X$ 的子段是单调不增的,这样就满足二分的单调性。

这样我们就把查找问题转换为了判定问题。

这样，我们就可以假设 $X$ 已经给定了,那么加下来就是求这个序列中是否存在长度不小于 $F$ 且平均值不小于 $X$ 的子段了。

我们先一步一步解决这个问题:

1. 如何判定一个子段的平均值是否至少为 $X$ 呢？

我们先将这个问题转换为数学式子:

$$\frac{a_l+a_{l+1}+a_{l+2}…+a_{r}}{r-l+1}\ge X$$
变换得:
$$(a_l-X)+(a_{l+1}-X)+(a_{l+2}-X)…+(a_r-X)\ge 0$$
( 其中$a$数组为子段, $l$ 和 $r$ 分别为子段的左右端点。)

这样就可以先把字段中所有数先减去一个 $X$ 再相加，最后判断区间和是否不小于 $0$ 了。

我们就可以用前缀和来处理了, 注意!前缀和数组存储的不是原来的数字,而是存储给出的数列中的数字减去 $X$ 的差

2. 如何判定是否存在平均值至少为 $X$ 的子段呢？

首先就可以想到枚举左右端点,但是太浪费时间了,因为我们是求是否存在满足条件的子段,所以我们可以只找最佳的子段。所谓最佳,就是使平均数最大,所以可以只枚举右端点 (1~n),而左端点就可以用前缀最小值的位置,这样就解决了这一个问题。

为什么左端点就可以用前缀最小值的位置呢？

因为求区间和是用左端点减去

3. 如何判定是否存在平均值至少为 $X$ 且长度至少为 $F$ 的子段呢？

这个非常好解决,只需将枚举右端点的范围改为从 $F$ 到 $N$ ,前缀最小值维护的位置改为当前右端点的位置减去 $F$ 就可以了。

总结:

首先二分一个平均值 $X$ ,然后用前缀和数组存储序列中的数字减去 $X$ 的前缀和,再枚举右端点 (从1~n),而左端点是前缀最小值 (当前右端点的位置减去 $F$ ) 的位置,再用前缀和求这个区间和,再判断这个区间和是否不小于 $0$ ,只要在枚举过程中,至少有一个区间和不小于 $0$ 这个 $X$ 就是合法的,否则不合法。

参考代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
double a[MAXN],sum[MAXN];
int n,f;
bool check(double x){
    for(int i=1;i<=n;i++){
        sum[i]=a[i]-x+sum[i-1];//存储给出的数列中的数字减去X的差
    }
    double ans=INT_MIN,mins=INT_MAX;
    for(int i=f;i<=n;i++){
        mins=min(sum[i-f],mins);//使用前缀最小值的位置作为左端点
        ans=max(ans,sum[i]-mins);//存储区间和
    }
    return ans>=0;//判断是否合法
}
int main(){
    cin>>n>>f;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    double eps=1e-6,l=1,r=2000;//因为题目要求乘以1000再向下取整,其实就相当于保留4位小数,而eps是定义为1e-(要求保留的位数+2)
    while(l+eps<r){//因为是实数二分,所以l要加上精度eps
        double mid=(l+r)/2;//同样，因为是实数二分所以不能使用右移运算
        if(check(mid)){
            l=mid;
        }else{
            r=mid;
        }
    }
    cout<<(int)(r*1000)<<endl;//注意精度问题
    return 0;
}