最佳牛围栏 - 二分

电玩女神 2022-03-20 01:57 216阅读 0赞

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

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

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

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

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

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

**输出格式**  
输出一个整数，表示围起区域内每块地包含的牛的数量的平均值可能的最大值乘以1000得到的数值。

**数据范围  
1≤N≤100000  
1≤F≤N  
时/空限制： 1s / 64MB**

**输入样例：**  
10 6  
6  
4  
2  
10  
3  
8  
5  
9  
4  
1  
**输出样例：**  
6500

**解题思路：**

1.  转化为判定问题。因为直接求解不好求解，但是判定是不是存在一个比当前的mid更优的mid，是好判断的，所以把求解最优平均值 转化为 判断是否有比当前平均值的更优平均值。— O(lg(L))
2.  判定问题的策略。有没有比mid更优的解.  
    \+将序列中的数都减去一个mid，此时问题转变为存不存在一段比F长的序列，连续子段和是正数。 — O(N)  
    \+利用前缀和，判断存不存在连续子段和大于0.—O(N)

判定次数为lg(L)次，L是答案区间的长度，判定过程在O(N)的时间就可以完成，所以总的时间复杂度是  
O(N \* lg(L)), 是可以接受的。

**详细代码**

#include <iostream>
    #include <algorithm>
    #include <cstring>
    
    using namespace std;
    
    #define esp 1e-9
    
    const int N = 100010;
    
    int n,f;
    int a[N];
    double mid, l, r;
    
    bool check(double m)
    {
        
        double s[N];
        memset(s, 0, sizeof s);
        for(int i = 1;i <= n;i++)
        {
        
            s[i] = s[i - 1] + a[i] - m; 
        }
        double ans = -1e6;
        double minres = 0x3f3f3f3f;
        for(int i = f;i <= n;i++)
        {
        
            minres = min(minres, s[i - f]);
            ans = max(ans, s[i] - minres);
        }
        return ans > 0;
    }
    
    int main()
    {
        
        cin >> n >> f;
        for(int i = 1;i <= n;i++)
            cin >> a[i];
        
        l = -1e6;
        r = 1e6;
        while(r - l > esp)
        {
        
            mid = (l + r) / 2;
            if(check(mid))
                l = mid;
            else 
                r = mid;
            //cout << r * 1000<< endl;
        }
        // 注意要取右区间，
        cout << (long long)(r * 1000) << endl;
    }