POJ2018 Best Cow Fences-程序员宅基地

我对二分的理解：https://www.cnblogs.com/AKMer/p/9737477.html

题目传送门：http://poj.org/problem?id=2018

我们二分一个平均数，设\(a\)数组每个数减去平均数为\(b\)数组，若\(b\)数组当中存在某一段长度大于\(k\)并且这一段权值和大于\(0\)，那么说明最终平均值肯定大于我们当前二分的平均值。

那么怎么求\(b\)数组当中权值和大于\(0\)且长度大于\(k\)的一段呢？显然这样的段我们可以这样枚举：

for(int i=1;i<=n;i++)
    for(int j=0;j<=i-k;j++)
        if(sum[i]-sum[j]>0)return 1;

但是这个\(n^2\)做法显然不行。我们可以发现，以\(i\)结尾的段落，设\(mn\)是\(sum[0]～sum[i-k]\)当中的最小值，只要\(sum[i]-mn>0\)就行了。所以我们只需要在\(i+1\)的时候，把\(mn\)与\(sum[i-k+1]\)取\(min\)就行了。

时间复杂度：\(O(nloga)\)

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>
#include <algorithm>
using namespace std;

const double eps=1e-6;
const int maxn=1e5+5;

int n,k;
int a[maxn];
double sum[maxn];

int read() {
    int x=0,f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
    return x*f;
}

bool check(double ave) {
    for(int i=1;i<=n;i++)
        sum[i]=sum[i-1]+(double)a[i]-ave;
    double mn=0;
    for(int i=k;i<=n;i++) {
        if(sum[i]-mn>0)return 1;
        mn=min(mn,sum[i-k+1]);
    }
    return 0;
}

int main() {
    double l=1e9,r=-1e9;
    n=read(),k=read();
    for(int i=1;i<=n;i++) {
        a[i]=read();
        l=min(l,(double)a[i]);
        r=max(r,(double)a[i]);
    }
    while(l+eps<r) {
        double mid=(l+r)/2;
        if(check(mid))l=mid;
        else r=mid;
    }
    printf("%d\n",(int)(r*1000));//因为平均值肯定比l大，所以输出r*1000
    return 0;
}