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 三月綠色

思路#

二分那個平均數，看數列的平均數是否能大於猜的平均數

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;
}