AcWing 102：最佳牛围栏 ← 二分+前缀和

【题目来源】
https://www.acwing.com/problem/content/104/

【题目描述】
农夫约翰的农场由 N 块田地组成，每块地里都有一定数量的牛，其数量不会少于 1 头，也不会超过 2000 头。
约翰希望用围栏将一部分连续的田地围起来，并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。
围起区域内至少需要包含 F 块地，其中 F 会在输入中给出。
在给定条件下，计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。

【输入格式】
第一行输入整数 N 和 F，数据间用空格隔开。
接下来 N 行，每行输入一个整数，第 i+1 行输入的整数代表第 i 片区域内包含的牛的数目。

【输出格式】
输出一个整数，表示平均值的最大值乘以 1000 再向下取整之后得到的结果。

【数据范围】
1≤N≤100000
1≤F≤N

【输入样例】
10 6
6 
4
2
10
3
8
5
9
4
1

【输出样例】
6500

【算法分析】
二分法、三分法，通常适用于求解具有单调性的问题。
若二分法失效，甚至需要考虑引入三分法。三分法实际就是二分法的扩展，即三分法将搜索范围分成三个部分 [le, lmid]、[lmid, rmid]、[rmid, ri]，而不是两个。

三分法的代码模板如下所示：

while(ri-le>eps){
    double lmid=le+(ri-le)/3.0;
    double rmid=ri-(ri-le)/3.0;

    if(f(lmid)<f(rmid)) le=lmid;
    else ri=rmid;
}

【算法代码】

#include <bits/stdc++.h>
using namespace std;

const int inf=0x3f3f3f3f;
const int maxn=1e5+5;
double a[maxn],s[maxn];
double imin,ans;
int n,f;

double check(double avg) {
    imin=inf;
    ans=-inf;
    for(int i=1; i<=n; i++) s[i]=s[i-1]+a[i]-avg;
    for(int i=f; i<=n; i++) {
        imin=min(imin,s[i-f]);
        ans=max(ans,s[i]-imin);
    }
    return ans;
}

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


/*
in:
10 6
6
4
2
10
3
8
5
9
4
1

out:
6500
*/

【参考文献】
https://blog.csdn.net/weixin_43872728/article/details/105382365
https://www.cnblogs.com/guiyou/p/15110706.html