题目传送门
【题目大意】
有$N$块土地，第$i$块土地有$A_i$头牛，选出连续的至少$F$块土地，使得平均每块土地上牛的数量最大。
【思路分析】
二分转化求值为判定，即二分出平均数$mid$，判定“是否存在一个长度不小于$F$的子段，子段和非负”。这题有一点特殊的地方就是有长度限制，对于子段和，我们可以用前缀和解决，首先想到可以这样：
$$max\{sum_i-min\{sum_j\}(0\le j\le i-F)\}(F\le i<n)$$
但是这样复杂度太大，所以我们要考虑如何简化。发现随着$i$的增长，$j$的取值范围每次只会增大1，即每次只会有一个新的值进入候选集合$min\{sum_j\}$，所以没有必要每次循环枚举$j$，只要用一个变量记录当前最小值，每次与新的取值取$min$就可以了。
【代码实现】
1 #include<cstdio> 2 #include<iostream> 3 #define rg register 4 #define go(i,a,b) for(rg int i=a;i<=b;i++) 5 using namespace std; 6 const int N=100002; 7 double a[N],s[N],b[N]; 8 int n,f; 9 int main(){ 10 scanf("%d%d",&n,&f);double maxn=0; 11 go(i,1,n) scanf("%lf",&a[i]),maxn=max(maxn,a[i]); 12 double l=s[n]/n,r=(double)maxn; 13 while(r-l>1e-5){ 14 double mid=(l+r)/2; 15 go(i,1,n) b[i]=a[i]-mid,s[i]=s[i-1]+b[i]; 16 double ans=-N,minn=N; 17 go(i,f,n){ 18 minn=min(minn,s[i-f]); 19 ans=max(ans,s[i]-minn); 20 } 21 if(ans>=0) l=mid;else r=mid; 22 } 23 cout<<int(r*1000)<<endl; 24 return 0; 25 } 代码戳这里转载于:https://www.cnblogs.com/THWZF/p/11248002.html
相关资源：JAVA上百实例源码以及开源项目