POJ 2018|最高の牛フェンス

POJ 2018 | 最高の牛のフェンス#

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

説明#

ファーマー・ジョンの農場は、N（1 <= N <= 100,000）フィールドの長い列で構成されています。各フィールドには、1 <= ncows <= 2000 の特定の数の牛が含まれています。

FJ は、ブロック内のフィールドごとの平均牛数を最大化するために、これらのフィールドの連続したグループの周りにフェンスを建てたいと考えています。このブロックには、F（1 <= F <= N）フィールドが少なくとも含まれている必要があります。F は入力として与えられます。

制約を考慮して、平均を最大化するフェンスの配置を計算します。

入力#

* 行 1: スペースで区切られた 2 つの整数、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;
}