Best Cow Fence

题目描述

农场主 John (简称 FJ) 的农场有一长排的 N (1 <= N <= 100,000)块地组成. 每块地有一定数量 (ncows) 的牛, 1 <= ncows <=2000.

FJ 想修建环绕邻接的一组地块的栅栏, 以最大化这组地块中平均每块地中牛的个数.

这组地块必须包含至少 F (1 <= F <= N) 块地, F 作为输入给出.

给定约束, 计算出栅栏的布置情况以最大化平均数.

友情提示：由于本题过于陈旧，数据上有一些偏差，请在解答的时候精度设为"1e-5".

输入格式

第一行: 空格分隔的两个整数, N 和 F.

第2到第N+1行: 每行包含一个整数, 一块地中的牛数. 行 2 给出地块 1 中的牛数, 行 3 给出地块 2 中的牛数, ...

输出格式

一行一个整数, 它是最大平均数的 1000 倍.

不要用舍入求整, 仅仅输出整数

样例数据

input

output

数据规模与约定

时间限制：

空间限制：

　　这道题出自算法进阶，可能作为新手，我在看了lyd大佬的代码才搞明白这道题的意思。

　　简单了解题目我们把题目可化简为：在长不小于l的区间里找到最打的平均值。

　　在求最大子段和（相关链接https://www.cnblogs.com/fuhuayongyuandeshen/p/14186433.html）的思路中我们可以得知我们可以通过二分枚举答案，将所有a数组里的数减去mid，求出前缀和，再判断答案是否合理就可以了。

代码如下：

　　#include<bits/stdc++.h>

using namespace std;
double a[100030],b[102000],sum[105001];
int n,L;
int main()
{
// freopen("cowfnc.in","r",stdin);
// freopen("cowfnc.out","w",stdout);
　　cin>>n>>L;
　　for(int i=1;i<=n;i++)
　　scanf("%lf",&a[i]);
　　double l=0,r=1e6;//书上将l设为-1e6，是一样的。

　　while(r-l>1e-5)//确定精度
　　{
　　　　double mid=(r+l)/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 ans=-2141244;
　　　　double num=2142144;//随便设个较大的
　　　　for(int i=L;i<=n;i++)
　　　　{
　　　　　　num=min(num,sum[i-L]);
　　　　　　ans=max(ans,sum[i]-num);
　　　　}//判断是否合法
　　　　if(ans>=0)
　　　　l=mid;
　　　　else
　　　　r=mid;
　　}
　　cout<<int(r*1000);
　　return 0;
}