POJ 2018|最佳牛栏围栏

POJ 2018 | 最佳牛栏#

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

描述#

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

FJ 想要在这些田地中围起一个连续的区域，以最大化该区域内每个田地的平均牛数。该区域必须至少包含 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;
}