idea

题目描述

农夫约翰的农场由 N 块田地组成，每块地里都有一定数量的牛,其数量不会少于1头，也不会超过2000头。

约翰希望用围栏将一部分连续的田地围起来，并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。

围起区域内至少需要包含 F 块地，其中 F 会在输入中给出。

在给定条件下，计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。

输入格式
第一行输入整数 N 和 F ，数据间用空格隔开。

接下来 N 行，每行输出一个整数，第i+1行输出的整数代表，第i片区域内包含的牛的数目。

输出格式
输出一个整数，表示平均值的最大值乘以1000再 向下取整 之后得到的结果。

数据范围
1≤N≤100000
1≤F≤N

输入样例：

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

输出样例：

6500

算法1

C++ 代码

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, f, cows[N];
double sum[N];

int check(double m) {
    for(int i = 1; i <= n; i++) {
        sum[i] = cows[i] - m;
        sum[i] += sum[i - 1];
    }
    double minv = 0;
    for(int i = f, j = 0; i <= n; i++) {
        if(i - j < f) continue;
        minv = min(minv, sum[j]);
        if(sum[i] - minv >= 0) return 1;
        else j++;
    }
    return 0;
}

int main() {
    cin >> n >> f;
    for(int i = 1; i <= n; i++)  cin >> cows[i];
    double l = 1, r = 2000;
    while(r - l > 1e-8) {
        double m = l + (r - l) / 2;
        if(check(m)) l = m;
        else r = m;
    }
    cout << (int)(r * 1000) << endl; 
    return 0;
}