【二分】Best Cow Fences

本文主要是介绍【二分】Best Cow Fences，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

$Description$

农夫约翰的农场由一长排N (1 <= N <= 100,000)块地组成。每个字段包含一定数量的奶牛，1 <= ncows <= 2000。FJ想要在一组相邻的牧场周围建一个篱笆，以便最大化该街区内每块牧场的平均奶牛数量。块必须包含至少F (1 <= F <= N)字段，其中F作为输入。在给定约束条件下，计算使平均值最大化的栅栏位置。

$Input$

第1行:两个空格分隔的整数，$N$和$f$
第2行:$N+1$:每一行包含一个整数，即字段中奶牛的数量。

$Output$

第1行:一个整数，它是最大平均值的$1000$倍。不执行四舍五入，只打印$1000\ast ncows/nfields$的整数。

$SampleInput$

10 6
6 
4
2
10
3
8
5
9
4
1

$SampleOutput$

6500

思路

二分平均值
然后每个数减去$Mid$
然后求最长非负子序列

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
double A[100250],B[100250],Sum[100250];
int n,m;
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;++i)scanf("%lf",&A[i]);double F=1e-5;//精度，我也不知道double l=-1e6,r=1e6;while(r-l>F){double Mid=(l+r)/2;for(int i=1;i<=n;++i)//减去平均值B[i]=A[i]-Mid;for(int i=1;i<=n;++i)//前缀和Sum[i]=Sum[i-1]+B[i];double Min=1e10,Ans=-1e10;for(int i=m;i<=n;++i){Min=min(Min,Sum[i-m]);Ans=max(Ans,Sum[i]-Min);}if(Ans>0)l=Mid;else r=Mid;}printf("%d",int(r*1000));return 0;
}

这篇关于【二分】Best Cow Fences的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---