题解-最*牛围栏-二分+双指针

• • 题目
  • 思路
  • 实现
  • 错误原因

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

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

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

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

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

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

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

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

AcWing-题目链接

首先题意为在一段序列中，寻找连续并数量不小于 f 的序列平均值最大。根据数据规模可知算法时间复杂度要小于 O ( n log ⁡ n ) O(nlog n) O(nlogn)。暴力寻找区间时间复杂度为 O ( n 2 ) O(n^2) O(n2) ，会超时。
改题目直接求解区间位置并不好求解，故可以尝试利用二分求解，并验证二分结果是否正确。然后问题就转换为在一段序列中是否能找到区间范围大于 f 的一段序列平均值大于等于二分值。求解一段序列和可以利用前缀和简化，面对平均值问问题时可以讲数组每个值均减去平均值。最后利用双指针计算是否满足条件即可。

时间复杂度： O ( n log ⁡ n ) O(nlog n) O(nlogn)

#include
using namespace std;

int num[100009];
double ck[100009];
int n,f;

int check(double avg)
{
    //减去平均值 并计算前缀和
    for(int i=1;i<=n;i++) ck[i]=ck[i-1]+num[i]-avg;
    
    //双指针求解
    double i=0;
    for(int j=f;j<=n;j++)
    {
        i=min(i,ck[j-f]);
        if(ck[j]-i>=0)
            return 1;
    }
    return 0;
}

int main()
{
    scanf("%d%d",&n,&f);
    
    double r=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&num[i]);
        r=max(r,(double)num[i]);
    }
    
    double l=0;
    while(r-l>1e-6)
    {
        double mid=(r+l)/2;
        if(check(mid))
            l=mid;
        else
            r=mid;
    }
    printf("%d",int(r*1000));
    
    return 0;
}

第一次看到该题时，首先是没看到限制条件 选取的长度>=F 这个限制条件，误以为是等于F。在之后的调试中发现题目的限制条件出错，并想利用dp做辅助求解出在选取 (j-f+1,j) 区间时是否选取 j-f+1 之前的数据。最后发现求解的 dp[j] 并不是代表------------------------------------------------