POJ 2018 | 最佳牛栏

POJ 2018 | 最佳牛栏#

~~都 9102 年了我做的题怎么题号还是 8102~~

描述#

农夫约翰的农场由一排长长的 N（1 <= N <= 100,000）个田地组成。每个田地里都有一定数量的牛，1 <= ncows <= 2000。

约翰想要在一组连续的田地周围建造一个栅栏，以便在该区块内最大化每个田地的平均牛数。该区块必须包含至少 F（1 <= F <= N）个田地，其中 F 作为输入给出。

计算在给定约束条件下最大化平均值的栅栏位置。

输入#

* 第 1 行：两个以空格分隔的整数 N 和 F。

* 第 2 行至第 N+1 行：每行包含一个整数，表示一个田地中的牛的数量。第 2 行表示第 1 个田地中的牛的数量，第 3 行表示第 2 个田地中的牛的数量，依此类推。

输出#

* 第 1 行：一个整数，表示最大平均值的 1000 倍。不要进行四舍五入，只需打印 1000*ncows/nfields 的整数部分。

示例输入#

示例输出#

来源#

USACO 2003 年 3 月绿色

思路#

二分查找平均数，看数列的平均数是否大于猜测的平均数。

check 函数如何编写：

? 将每个数减去当前猜测的平均数，然后寻找一个长度大于 F 且和大于 0 的子数列，那么此数列的平均值肯定大于 x。

check 函数的代码（感谢 lqx 大佬）：

bool check(double x)
{
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;++i)
    {
        b[i]=(a[i]-x+b[i-1]);
    }
    double minsum=0;
    for(int i=f;i<=n;++i)
    {
        minsum=min(minsum,b[i-f]);//记录f项之前最小的前缀和
        double tmp=b[i]-minsum;//所以此时tmp是和最大的子序列的和
        if(tmp>0)return true;
    }
    return false;
}

以下是我 PAC 的 dp 代码：

//dp1：和
//dp2：以i结尾的最大连续和的长度
bool check(double x)
{
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;++i)
    {
        b[i]=(a[i]-x);
    }
    for(int i=1;i<=n;++i)
    {
        if(dp[i-1]>0)
        {
            dp[i]=dp[i-1]+b[i];
            dp2[i]=dp2[i-1]+1;
        }
        else
        {
            dp[i]=b[i];
            dp2[i]=1;
        }
        if(dp[i]>=0&&dp2[i]>=f)return 1;
    }
    return false;
}

代码#

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#define mid (l+r)/2
#define int long long
using namespace std;

const int MAXN=100000+5;

int n,f;
int a[MAXN];
double b[MAXN];
int dp[MAXN],dp2[MAXN];

bool check(double x);

#undef int
int main()
{
    #define int long long
    scanf("%lld%lld",&n,&f);
    double l=0,r=2000000;
    for(int i=1;i<=n;++i)
    {
        scanf("%lld",a+i);
        a[i]*=1000;
    }

    while(fabs(l-r)>1e-4)
    {
        if(check(mid))
        {
            l=mid;
        }
        else
            r=mid;
    }
    printf("%lld\n",(int)r);
    return 0;
}

bool check(double x)
{
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;++i)
    {
        b[i]=(a[i]-x+b[i-1]);
    }
    double minsum=0;
    for(int i=f;i<=n;++i)
    {
        minsum=min(minsum,b[i-f]);
        double tmp=b[i]-minsum;
        if(tmp>0)return true;
    }
    return false;
}