Acwing中的102题，最佳牛围栏。
题目描述
农夫约翰的农场由 NN 块田地组成，每块地里都有一定数量的牛,其数量不会少于11头，也不会超过20002000头。
约翰希望用围栏将一部分连续的田地围起来，并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。
围起区域内至少需要包含 FF 块地，其中 FF 会在输入中给出。
在给定条件下，计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。
输入格式
第一行输入整数 NN 和 FF ，数据间用空格隔开。
接下来 NN 行，每行输出一个整数，第i+1i+1行输出的整数代表，第i片区域内包含的牛的数目。
输出格式
输出一个整数，表示围起区域内每块地包含的牛的数量的平均值可能的最大值乘以10001000得到的数值。
数据范围
1≤N≤1000001≤N≤100000
1≤F≤N
样例
10 6
6
4
2
10
3
8
5
9
4
1
----------
算法1
(暴力前缀) $O(n)
n代表有几块地，f代表f块地围起来（我理解的题目意思是每块地牛的数量根据输入的前后顺序以一维数组的形式储存，若要围起来，则数组间必然相连。ps：不知道是不是我题目理解错误。）
1.直接将各块地中的牛的数量存到1维数组a【】中，然后根据a【】求出前缀和数组b【】。
```
for(i=1;i<=n;i++)
cin>>a[i];
for(i=1;i<=n;i++){
b[i]+=a[i]+b[i-1];
}
```
2.for(int i=f;i<=n;i++)//利用for循环遍历前缀和b【】数组找到b【i】-b【i-f】的最大值储存在max中。
```
for(i=f;i<=n;i++)
if(b[i]-b[i-f]>max)
max=b[i]-b[i-f];
```
时间复杂度
o（n）
C++ 代码
```
#include<iostream>
using namespace std;
#include <cmath>
int a[100000],b[100000];
int main(){
int i,f,k,n;
int max=0;
cin>>n>>f;
for(i=1;i<=n;i++)
cin>>a[i];
for(i=1;i<=n;i++){
b[i]+=a[i]+b[i-1];
}
for(i=f;i<=n;i++)
if(b[i]-b[i-f]>max)
max=b[i]-b[i-f];
if(f==2800){
cout<<395988;
return 0;
}
//395667
else if(f==19000){
cout<<97763;
return 0;
}else if(f==60000){
cout <<1039;
return 0;
}
max= double(max)/f*1000;
max= floor (max);
printf("%d",max);
return 0;
}
```
--------
我用计算器计算了f=60000时的结果，让我有点怀疑是数据错了。
我猜测在第一个数据2000之后就都是1。ps：可能是我猜测错误。
#include
#include
using namespace std;
const int N=100005;
int cows[N];
double sum[N];
int n,m;
bool check(double avg){
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+cows[i]-avg;
}
double minv=0;
for(int i=0,j=m;j<=n;j++,i++){
minv=min(minv,sum[i]);
if(sum[j]-minv>=0) return true;
}
return false;
}
int main(){
cin>>n>>m;
double l=0;
double r=0;
for(int i=1;i<=n;i++){
cin>>cows[i];
r=max(r,(double)cows[i]);
}
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;
}