【POJ 2018】 Best Cow Fences

【题目链接】

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

【算法】

二分平均值

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

【代码】

#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include <set>  
#include   
#include   
#include   
#include <string>  
#include   
#include   
#include   
#include   
#include   
#include  
using namespace std;
#define MAXN 100010
const double eps = 1e-5;

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 = 1; i <= n; i++) b[i] = a[i] - x;
        for (i = 1; i <= n; i++) s[i] = s[i-1] + b[i];
        for (i = f; i <= n; i++)
        {
                mn = min(mn,s[i-f]);
                ret = max(ret,s[i]-mn);
        }        
        return ret >= 0;
}

int main() {
        
        scanf("%d%d",&n,&f);
        for (i = 1; i <= n; i++) scanf("%lf",&a[i]);
        l = -1e6; r = 1e6;
        while (r - l > eps)
        {
                mid = (l + r) / 2;
                if (check(mid)) l = mid;
                else r = mid;
        }
        printf("%d\n",int(r*1000));
        
        return 0;
    
}

二分

【POJ 2018】 Best Cow Fences

相关

牛客练习赛91（并查集+二维偏序+二分）

数据结构与算法之PHP查找算法（二分查找）

二分查找模板（准确找定值）

浅谈二分的边界问题

算法之二分法

The 2021 CCPC Guilin Onsite【A,I,G(二分),D（思维+构造）,E（最短路】

leetcode-二分查找相关

二分查找算法细节详解

c_mt_找有k个数小于自己的数（二分->复杂化 / 排序简化）

二分搜索的变形

leetcode154. 寻找旋转排序数组中的最小值 II（二分）

二分查找

标签