POJ 2018 Best Cow Fences 题解【二分答案】【前缀和】【分数规划】

点击量：393

    这个二分答案不是很好想，而且卡精度……

目录

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

Source

USACO 2003 March Green

题意：

    给出\(n\)个连续的农场，每个农场里有\(ncows\)只奶牛，求出一段农场使得：段长度不小于给定的\(F\)，且这一段中奶牛数量的平均值最大。

题解：

    这个题目的难点在于平均值最大。而随着区间长度变化，平均值的分母也在变，因此不是线性的，不能直接贪心或者DP。但是平均值可以联想到分数规划。

    这里\(k=\frac{\sum_{i=1}^n a_i\times x_i}{\sum_{i=1}^n b_i\times x_i}\)中，\(a_i\)是每个农场中奶牛的数目，\(b_i\)总是\(1\)。我们二分这个\(k\)，那么每个农场的贡献就是\(a’_i=a_i-kb_i=a_i-k\)。因此我们要求出是否存在一段\(a’_i\sim a’_{i+m}\)，使得\(sum_{i+m}-sum{i-1}\ge 0\)，且\(m\ge F\)。

    对于一个子段\([i,j]\)，它的和如果非负，说明\(sum_j-sum{i-1}\ge 0\)。那么我们可以枚举\(j\)和\(1\le i\le j-m\)，检查有没有\(sum_j-sum_i\ge 0\)，如果有，就返回true，检验完之后没有就返回false，其余和分数规划类似。

    这样的时间复杂度为\(O(n^2\log n)\)，实际上随着\(j\)增大，\((j-m)\)也是在依次增加的。这样我们就可以用前缀和优化，使用minn变量存下当前合法区间\(1\le i\le j-m\)中最小的\(sum_i\)，再用正在枚举的\(sum_j\)减去它，更新答案。时间复杂度为\(O(n\log n)\)。

    这题有点卡精度……而且有一种神秘的斜率优化\(O(n)\)做法，可见周源的2004年国家集训队论文。

Code：

#include<cstdio>
#include<cstring>
#define eps 1e-7
double sum[100100];
int a[100100],n,m;
bool check(double x)
{
    sum[0]=0;
    for(int i=1;i<=n;++i)
        sum[i]=sum[i-1]+a[i]-x;
    double minn=0;
    for(int i=m;i<=n;++i)
    {
        if(sum[i]-minn>0)
            return true;
        minn=minn<sum[i-m+1]?minn:sum[i-m+1];
    }
    return false;
}
int main()
{
    //freopen("data.in","r",stdin);
    //freopen("bf.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        sum[0]+=a[i];
    }
    double l=0,r=sum[0],mid;
    while(r-l>eps)
    {
        mid=(l+r)/2.0;
        if(check(mid))
            l=mid;
        else
            r=mid;
    }
    int ans=r*1000;//好像只有输出r并向下取整才能正确……不知道为什么
    printf("%d\n",ans);
    return 0;
}