Best Cow Fences题解

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

Farmer John's farm consists of a long row of N(1≤N≤100,000)fields. Each field contains a certain number of cows,1≤ncows≤2000.
FJ wants to build a fence around a contiguous group of these fields in order to maximize the average number of cows per field within that block. The block must contain at least F (1≤F≤N)) fields, where F given as input.
Calculate the fence placement that maximizes the average, given the constraint.

输入描述:

* Line 1: Two space-separated integers, N and F.
* Lines 2..N+1: Each line contains a single integer, the number of cows in a field. Line 2 gives the number of cows in field 1,line 3 gives the number in field 2, and so on.

输出描述:

* Line 1: A single integer that is 1000 times the maximal average.Do not perform rounding, just print the integer that is 1000×ncowsnfieldsfrac{1000times ncows}{nfields}nfields1000×ncows​.

示例1

输入

10 6
6 
4
2
10
3
8
5
9
4
1

输出

6500

二分答案

AC代码：

#include 
using namespace std;
const double eps = 1e-5;
double a[100010],b[100010],sum[100010];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,L;
    cin >> n >> L;
    for(int i = 1;i <= n;i++) cin >> a[i];
    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 * 1e3) << endl;
    return 0;
}