POJ 2018|Best Cow Fences

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

Description

Farmer John’s farm consists of a long row of N (1 <= N <= 100,000)fields. Each field contains a certain number of cows, 1 <= ncows <= 2000.

FJ wants to build a fence around a contiguous group of these fields in order to maximize the average number of cows per field within that block. The block must contain at least F (1 <= F <= N) fields, where F given as input.

Calculate the fence placement that maximizes the average, given the constraint.

Input

* Line 1: Two space-separated integers, N and F.

* Lines 2…N+1: Each line contains a single integer, the number of cows in a field. Line 2 gives the number of cows in field 1,line 3 gives the number in field 2, and so on.

Output

* Line 1: A single integer that is 1000 times the maximal average.Do not perform rounding, just print the integer that is 1000*ncows/nfields.

Sample Input

Sample Output

Source

USACO 2003 March Green

思路

二分那个平均数，看数列的平均数是否能大于猜的平均数

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

Code

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