---
title: "最佳牛围栏"
created: 2025-11-28
tags:
  - 算法
---

# 最佳牛围栏

## 题目 [最佳牛围栏](https://www.acwing.com/problem/content/description/104/)

![[image-5361df9d.png]]

## 思路分析

最大平均数在0~2000之间 且具有单调性

可以用二分去找到 还是假设它为x

(一个平均数的小技巧 将原数组的值全减去平均数 可以构造出一个新的数组 方便计算)

把所有数减去这个x 因为x是最大平均数

所以肯定就剩下少数几段的和≥0 答案肯定在里面 范围一下就缩小了很多

将这个处理过的数组构造前缀和

要看某段的和是否大于等于0

就只要用s[r]-s[l-1]≥0即可

其中l和r相差F

但是这样的话就只考虑得到F块地 对于至少F的条件没满足

发现其实s[r]-s[l-1]≥0 仅仅大于0是不够的 还得结果越大越好

那要结果越大 就得s[l-1]越小

公式化成s[r]≥s[l-1]*min*

也就是说 如果F长度以外 存在某个值让它比F长度的s[r]≥s[l-1]更大 那它才是最优解

这样一来就考虑到了>F的情况（假设F是3 这样就考虑到了4 5 的情况）

那么肯定就需要存储这个最小值

使用minv=min(minv,s[l-1])

公式化成 s[r]≥minv

不断去取mid判断这个条件

如果满足 说明某个平均数存在 它一定是在x的左边或者等于x 让l=mid

如果不满足 说明这个平均数肯定不存在 mid取大了 答案在左边 让r=mid

因为是浮点数二分 不存在什么加一的问题

## 代码实现

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

const int N=100010;
int n,F;
int cows[N];
double sum[N];

bool check(double mid){
    for(int i=1;i<=n;i++)
        sum[i]=sum[i-1]+cows[i]-mid;
    double minv=0;
    for(int i=1,j=F;j<=n;i++,j++){
        minv=min(minv,sum[i-1]);
        if(sum[j]>=minv)    return true;
    }
    return false;
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>F;
    for(int i=1;i<=n;i++)   cin>>cows[i];

    double l=0,r=2000;
    while(r-l>1e-5){
        double mid=(l+r)/2;
        if(check(mid))  l=mid;
        else    r=mid;
    }
    cout<<int(r*1000);
    return 0;
}
```

## 同类题型

## 视频讲解

- [[2-Learning/02-算法/03-刷题理模型/前缀和与差分相关模型/前缀和/最佳牛围栏|最佳牛围栏]]

---
⬅️ [[2-Learning/02-算法/03-刷题理模型/二分相关模型/无线网络|无线网络]] 🏠 [[00-刷题理模型]] ➡️ [[2-Learning/02-算法/03-刷题理模型/二分相关模型/最长连续子序列|最长连续子序列]]