二分、前缀和和双指针的混合应用

参考 题解

几个合理的解释：

1. 为什么要使用l=0,r=max(r,a[i])这样的式子来表示：
   因为假定的mid值一定在这个范围内
   最开始关于这个的想法是认为一定要尽可能使得最大值落在答案的区间内，但是其实不一定，虽然最大值可以尽最大可能拉高区间的平均值，但是可能周围的数实在太小导致平均值拉不起来，所以可能不如找一些分布密集的相对大数实惠
2. 在check函数的编写过程中，使用双指针的过程中每次循环会自动更新mi的值，因此mi值一定可以保证去到更长区间内的最小前缀和（为什么要从0开始取不得而知）

几个疑惑的问题：

1. 为什么mins写到for循环里面结果就会不一样
2. 为什么check函数返回true的条件为大于等于而不是大于
3. 为什么mins值只需要一行短短的min函数就可以实现
4. 为什么在check函数中的写法是n-f而不是n-f+1(从0开始)

#include<iostream>
#include<algorithm>

using namespace std;

const int N=1e5+10;
double a[N],s[N];
int n,f;

bool check(double avg){
    for(int i=1;i<=n;i++){
        //计算这个特殊的前缀和
        s[i]=s[i-1]+a[i]-avg;
    }

    double mins=0;
    //用j来表示后面的指针
    for(int j=f;j<=n;j++){
        //这里的mins用来表示满足条件的最小前缀和

        // for(int i=1;i<=n-f+1;i++){
        //     mins=min(mins,s[i]);
        // }
        //这里每次for循环都会更新这个值，因此一定可以去到所有之前的最小
        mins=min(mins,s[j-f]);

        //如果当前这段区间的所有数之和的值大于0，说明找到了一个均值大于当前avg的区间，直接返回true
        if(s[j]>=mins)  return true;
    }

    return false;
}

int main(){
    cin>>n>>f;

    double l=0,r=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        // a[i]+=a[i-1];
        r=max(r,a[i]);
    }

    while(r-l>1e-5){
        double mid=(l+r)/2;

        if(check(mid)){
            l=mid;
        }else{
            r=mid;
        }
    }


    cout<<int(r*1000);

    return 0;
}

/** 
 * 算法思想：
 * 1. 首先要把一个求最大值的最优化问题转化成一个判定问题，基于这一点变成一个二分的问题
 *      为什么可以二分呢？
 *      因为使用常规的双重for循环会超时，在优化问题的过程中，假设有一段长度不小于f的区间的平均值大于当前的假定值mid，就进行更新
 * 2. 在具体的判断是否存在这样的区间的过程中，可以在当前判断的区间范围中都减去一个mid，随后使用前缀和的方法来计算减去mid之后的区间
 * 和，如果区间和大于零，说明mid需要被更新
 * 3. 前缀和的具体实现过程中，由于要用到表达式：sum[j]-sum[i]>0，因此这个时候sum[i]越小越好，这里sum的含义是i在满足条件的区间内
 * 的拥有前缀和最小的
 */