前缀和+二分查找

二分查找使用场景：二分搜答案

二分查找要求
1.数是有范围的
2.是有序的
3.有反馈

解题思路
1.题目中要找到一个答案，可以正向计算，也可以反向查找（类似于找根），这里考虑使用二分搜答案。
2.在二分查找的使用要求中，该题目中我们已知平均数范围[1,2000]，故而重点在于第三条，如何判断与答案的大小关系。
3.牛群平均数公式使用一维前缀和表达为为:$$\frac{S_r-S_l}{r-l}$$
4.可以在用每一块土地的牛数目减去我们猜测的平均值，再算前缀和，即：s[i]=s[i-1]+(a[i]-x);。如果$max(S_r-S_l)>0$则说明我们所猜测的平均值过小，反之则过大。
5.不用找到$max(S_r-S_l)>0$进行判断，存在$S_r-S_l>0$即可说明我们所猜测的平均值过小。
6.使用双指针（或者也可以使用双重循环），进行$S_r-S_l$的计算，其中$r>F,l<n-F$。

⭐⭐
可以多看看双指针那里的实现方式

题解

#include<iostream>
#include<cstdio>

using namespace std;
const int N=1e5+10;
int n,f;
double a[N],s[N];

bool check(double x){
    for(int i=1;i<=n;i++){
        s[i]=s[i-1]+(a[i]-x);
    }
    double minv=0x3f3f3f3f;
    for (int i = 0, j = f; j <= n; j++, i++) {
        minv = min(minv, s[i]); 
        if(s[j] - minv >= 0) return true; 
    } return false; 

}


int main(){
    cin>>n>>f;
    for(int i=1;i<=n;i++) cin>>a[i];
    double l=1,r=2000;
    while(r-l>1e-5){
        double mid=(l+r)/2;
        if(check(mid)) l=mid;
        else r=mid;
    }
    cout<<(int)(r*1000)<<endl;

    return 0;
}