AcWing 102：最佳牛围栏 ← 二分+前缀和-Toy模板网

这篇具有很好参考价值的文章主要介绍了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]，而不是两个。

AcWing 102：最佳牛围栏 ← 二分+前缀和,信息学竞赛,# 分治算法,二分法,三分法

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

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

文章来源地址https://www.toymoban.com/news/detail-809573.html

到了这里，关于AcWing 102：最佳牛围栏 ← 二分+前缀和的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！