【POJ2018】Best Cow Fences

problem

给定一个正整数数列A，求一个平均数最大、长度不小于L的子段。

solution

二分判定：是否存在一个长度大于L，平均数不小于二分值的子段。

codes

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
double a[100001], b[100001], sum[100001];
int main(){
    int N, L;
    cin >> N >> L;
    for(int i = 1; i <= N; i++) scanf("%lf", &a[i]);
    double eps = 1e-5;
    double l = -1e6, r = 1e6;
    while(r - l > eps){
        double mid = (l + r) / 2;
        for (int i = 1; i <= N; i++) b[i] = a[i] - mid;
        for (int i = 1; i <= N; i++)
            sum[i] = (sum[i - 1] + b[i]);
        double ans = -1e10;
        double min_val = 1e10;
        for (int i = L; i <= N; i++) {
            min_val = min(min_val, sum[i - L]);
            ans = max(ans, sum[i] - min_val);
        }
        if (ans >= 0) l = mid; else r = mid;
    }
    cout << int(r * 1000) << endl;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/80457182