POJ 2018 | 最高の牛の柵

POJ 2018 | ベストカウフェンス#

~~もう 9102 年になったのに、私が解いた問題の番号はまだ 8102 です~~

説明#

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

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

制約が与えられた場合、平均を最大化するフェンスの配置を計算します。

入力#

* 行 1：2 つのスペースで区切られた整数 N と F。

* 行 2..N+1：各行には、フィールドの牛の数が 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;
}