【POJ 2018】 Best Cow Fences

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

【题目链接】

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

【算法】

二分平均值

检验时将每个数减去二分的值，求长度至少为L的子序列和的最大值，判断是否大于0

【代码】

#include <algorithm>

#include <bitset>

#include <cctype>

#include <cerrno>

#include <clocale>

#include <cmath>

#include <complex>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

#include <deque>

#include <exception>

#include <fstream>

#include <functional>

#include <limits>

#include <list>

#include <map>

#include <iomanip>

#include <ios>

#include <iosfwd>

#include <iostream>

#include <istream>

#include <ostream>

#include <queue>

#include <set>

#include <sstream>

#include <stdexcept>

#include <streambuf>

#include <string>

#include <utility>

#include <vector>

#include <cwchar>

#include <cwctype>

#include <stack>

#include <limits.h>

using namespace std;

#define MAXN 100010

const double eps = 1e-;

int n,f,i;

double a[MAXN],b[MAXN],s[MAXN];

double l,r,mid,ans;

inline bool check(double x)

{

        int i;

        double mn = 1e6,ret = -1e6;

        for (i = ; i <= n; i++) b[i] = a[i] - x;

        for (i = ; i <= n; i++) s[i] = s[i-] + b[i];

        for (i = f; i <= n; i++)

        {

                mn = min(mn,s[i-f]);

                ret = max(ret,s[i]-mn);

        }

        return ret >= ;

}

int main() {

        scanf("%d%d",&n,&f);

        for (i = ; i <= n; i++) scanf("%lf",&a[i]);

        l = -1e6; r = 1e6;

        while (r - l > eps)

        {

                mid = (l + r) / ;

                if (check(mid)) l = mid;

                else r = mid;

        }

        printf("%d\n",int(r*));

        return ;

}