POJ 2018 Best Cow Fences 解题报告

 

一、问题描述

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

10 6

6

4

2

10

3

8

5

9

4

1

Sample Output

6500

二、解题思路

问题等同于给一个数组，求数组中连续K（K>=F）个元素最大的平均值。设b[i]为以第i个元素结束的子段（长度>=F）的最大平均值，c[i]表示这个子段的元素个数。n[i]为以i结束的长度为F的子段的平均值。该问题的解就是b[i]中的最大值。

得到一个递推式：

b[i]=Max( b[i-1]*c[i-1]+a[i]/(c[i-1]+1),n[i]/F);

即如图所示，以第i+1个元素结尾的具有最大平均值的子段，不是上面那段，就是下面两段之和，取决于两者平均值的大小。

 

三、代码

#include<iostream>
using namespace std;
int a[100001];//a[i]

double b[100001];//b[i]表示以第i个元素结尾的子段的最大平均值

int n[100001];//n[i]表示以第i个元素结尾的长度为F的子段和

int c[100001];//c[i]表示以第i个元素结尾的最大平均值子段的元素个数

int Max(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    int N,F;
    cin>>N>>F;
    int i;
    for(i=1;i<=N;++i)
        cin>>a[i];
    n[F]=0;
    for(i=1;i<=F;++i)
        n[F]+=a[i];
    for(i=F+1;i<=N;++i)
    {
        n[i]=(n[i-1]-a[i-F]+a[i]);
    }
    b[F]=(double)n[F]/F;
    c[F]=F;
    for(i=F+1;i<=N;++i)
    {
        double temp;
        temp=(b[i-1]*c[i-1]+a[i])/(c[i-1]+1);
        double temp2=(double)n[i]/F;
        if(temp>temp2)
        {
            b[i]=temp;
            c[i]=c[i-1]+1;
        }
        else
        {
            b[i]=temp2;
            c[i]=F;
        }
    }
    int iMax=0;
    double dMax=0;
    for(i=F;i<=N;++i)
    {
        if(dMax<b[i])
            dMax=b[i];
    }
    iMax=dMax*1000;
    cout<<iMax<<endl;
    return 0;
}


优化后的代码

参考了这位哥们的代码：http://blog.csdn.net/x_chaos/archive/2010/03/15/5381454.aspx

#include<iostream>
using namespace std;
__int64 a[100001];
__int64 n[100001];
int main()
{
    __int64 N,F;
    __int64 sum,ct;
    __int64 nCows,nFields;
    scanf("%I64d%I64d",&N,&F);
    __int64 i;
    for(i=1;i<=N;++i)
        scanf("%I64d",&a[i]);
    n[F]=0;
    for(i=1;i<=F;++i)
        n[F]+=a[i];
    for(i=F+1;i<=N;++i)
    {
        n[i]=(n[i-1]-a[i-F]+a[i]);
    }
    nCows=sum=n[F];
    nFields=ct=F;
    for(i=F+1;i<=N;++i)
    {
        if((sum + a[i])* F < n[i] * (ct+1))
        {
            sum=n[i];
            ct=F;
        }
        else
        {
            sum+=a[i];
            ct=ct+1;
        }
        if(sum * nFields >nCows *ct)
        {
            nCows=sum;
            nFields=ct;
        }
    }
    printf("%I64d\n",1000*nCows/nFields);
    return 0;
}


四、结果分析

只需要遍历一次整个数组即可计算出结果，帮时间复杂度为O(n)，空间复杂度为O(n)。