欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【实数域上的二分,二分答案】POJ 2018 Best Cow Fences

程序员文章站 2022-05-08 17:57:21
...

链接

http://poj.org/problem?id=2018

大意

给定一些序列,求出长度至少为m的子序列的平均值最大

思路

因为奶牛的数量不可能为负数,所以该数据具有单调性,考虑二分

代码

#include<cstdio>
#include<algorithm>
#define eps (1e-5)
#define re register
#define r(i,a,b) for(re int i=a;i<=b;i++)
using namespace std;int n,m;
double a[100001],s[100001],l=-1e6,r=1e6;
inline bool check()//判断其平均值是否满足要求
{
    double minn=1e9;
    r(i,m,n) {minn=min(minn,s[i-m]);if(s[i]-minn>=0) return true;}//我们使左端点尽量小,右端点与左端点的差若能超过0说明满足要求
    return false;
}
signed main()
{
    scanf("%d%d",&n,&m);
    r(i,1,n) scanf("%lf",a+i);
    while(r-l>eps)
    {
        double mid=(l+r)/2;
        r(i,1,n) s[i]=s[~-i]+a[i]-mid;
        if(check()) l=mid;else r=mid;
    }
    printf("%d",(int)(r*1000));//输出
}