最佳牛围栏

题目：

农夫约翰的农场由 $N$ 块田地组成，每块地里都有一定数量的牛,其数量不会少于1头，也不会超过2000头。

约翰希望用围栏将一部分连续的田地围起来，并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。

围起区域内至少需要包含 $F$ 块地，其中 $F$ 会在输入中给出。

在给定条件下，计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。

输入格式
第一行输入整数 $N$ 和 $F$ ，数据间用空格隔开。

接下来 $N$ 行，每行输出一个整数，第$i+1$行输出的整数代表，第$i$片区域内包含的牛的数目。

输出格式

输出一个整数，表示围起区域内每块地包含的牛的数量的平均值可能的最大值乘以1000得到的数值。

数据范围

$1≤N≤100000$
$1≤F≤N$

输入样例

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

输出样例

6500

//=================以下可先略过

• 这题看上去不难，直接上代码（看不懂的话去看别的题解）

WA代码：

#include <bits/stdc++.h>
using namespace std;

int n,f;

double num[100010];

double mid_num[100010];


int judge(double avg)
{
    for(int i=1;i<=n;i++)
    {
        mid_num[i]=num[i]-avg;
        mid_num[i]+=mid_num[i-1];
    }

    double lef=0;
    double ans=-1e8;
    for(int i=f;i<=n;i++)
    {
        lef=min(lef,mid_num[i-f]);
        ans=max(ans,mid_num[i]-lef);
    }

    if(ans>=0)
        return 1;
    return 0;

}
int main()
{
    scanf("%d%d",&n,&f);
    for(int i=1;i<=n;i++)
        scanf("%lf",&num[i]);
    double l=0,r=2000;
    while(r-l>=0.000001)
    {
        double mid=(l+r)/2.0;
        if(judge(mid))
            l=mid;
        else
            r=mid;
    }
    cout<<(int)(l*1000)<<endl;
    return 0;
}

• 然后发现样例都过不了。。。

输出： 6499

• 然后恍然大悟

cout<<(int)(r*1000)<<endl;

• 你看，样例这不就过了吗

输出： 6500

• 然后——wa了（与答案差1）
• 最后在经过3小时以上的思考(其实什么都没有想出来) 及机房某国集学长的点拨后，终于想出了原因。为以防其它OIer掉入此坑，于是便替那位国集犇犇写下此篇题解

//===================以上可略过

进入正题

1. 最后取的应该是 l 而不是 r

• 当 judge()==1 时更新 l 所以l 一定成立
• 当 judge()==0 时更新 r 所以r 是不成立的

2. 但为什么样例过不了呢？其实这是一个提示 （坑），提示你精度不够。除非你用高精，不然double的精度无法满足此题。但也没必要写高精，你可以不直接输出答案而是算出大概值后再重新算一遍平均值

AC 代码

#include <bits/stdc++.h>
using namespace std;

int n,f;

double num[100010];

double mid_num[100010];


int judge(double avg)
{
    for(int i=1;i<=n;i++)
    {
        mid_num[i]=num[i]-avg;
        mid_num[i]+=mid_num[i-1];
    }

    double lef=0;
    double ans=-1e8;
    for(int i=f;i<=n;i++)
    {
        lef=min(lef,mid_num[i-f]);
        ans=max(ans,mid_num[i]-lef);
    }
    if(ans>=0)
        return 1;
    return 0;
}
int main()
{
    scanf("%d%d",&n,&f);
    for(int i=1;i<=n;i++)
        scanf("%lf",&num[i]);
    double l=0,r=2000;
    while(r-l>=0.000001)
    {
        double mid=(l+r)/2.0;
        if(judge(mid))
            l=mid;
        else
            r=mid;
    }
//==========================================================
//算出ans=l时的下标范围 id_l , id_r 
//然后再手动算一遍
    for(int i=1;i<=n;i++)
        mid_num[i]=num[i]-l,mid_num[i]+=mid_num[i-1];
    int mid_id=0;
    double lef=0;
    double ans=-1e8;
    int id_l=0;
    int id_r=n;
    for(int i=f;i<=n;i++)
    {
        if(lef>mid_num[i-f])
        {
            lef=mid_num[i-f];
            mid_id=i-f;
        }
        if(ans<mid_num[i]-lef)
        {
            ans=mid_num[i]-lef;
            id_l=mid_id;
            id_r=i;
        }
    }
    double sum=0;
    for(int i=id_l+1;i<=id_r;i++)
    {
        sum+=num[i];
    }
    cout<<(int)(sum*1000.0/(id_r-id_l))<<endl;
    return 0;
}