最佳牛围栏（实数二分）脑子完全不够用

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

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

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

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

输入格式

第一行输入整数 NN 和 FF，数据间用空格隔开。

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

输出格式

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

数据范围

1≤N≤1000001≤N≤100000
1≤F≤N1≤F≤N

输入样例：

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

输出样例：

6500

 基本思路：mid代表1到2000（牛的数量）之间的数，令每个数组中的数减去一个mid，若二分到的mid为最终答案，则数组中应该有且只有一个区间满足条件。

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 100010;
double s[N],cows[N];
int n, m;

bool check(double avg)
{
    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + cows[i] - avg;

//将每个数都减去一个mid，然后求前缀和。
    double minv = 0;

 //s[j]-minv>=0代表i到j的区间是大于0的，所以要找到一个最小的s[i]，是的i到j的和最大。
    for (int i = 0, j = m; j <= n; i++, j++)
    {

        minv=min(minv,s[i]);
        if (s[j] >= minv) return 1;//如果s[j]-minv>=0，则说明mid可以继续增大，左边界可以右移。
    }
    return 0;//否则mid应该减小，右端点左移。

}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> cows[i];
    double  l = 0, r = 2000;

//mid一定大于0小于2000，二分找到这一个mid。
    while (r - l > 1e-6)
    {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }
    cout << int (r * 1000) << endl;
    return 0;
}

最后

以上就是满意大地为你收集整理的最佳牛围栏（实数二分）脑子完全不够用的全部内容，希望文章能够帮你解决最佳牛围栏（实数二分）脑子完全不够用所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。