最佳牛围栏

题目描述：

给的题面看的很抽象，半天看不懂再说什么，我简化一下

给你一个长度为n的数组a[i]，你想求一段长度至少为m的连续的子数组所包含的数字和的平均值最大是多少

思路：

显然是要用二分答案，我们二分平均值mid，但是难就难在check函数

我们可以这样写check()函数：

对于每个a[i]，我们令b[i] = a[i]-mid，mid就是本次check的答案，如果b数组存在一个长度大于等于m，且数字和>=0的子区间则代表check成功，所以我们可以对b数组求一个前缀和pre，此时我们只需要找到一对l,r满足r-l>=m && pre[r]-pre[l-1]>=0即可，我们可以利用双指针，一个指针l从0开始枚举，维护前缀最小的pre，后一个指针r从m开始，判断是否满足条件，二者同时往后移动，这样保证了长度至少是m

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>

typedef long long ll;

#define MAX 300050
int n, m, k, x, y, z;
double tr[MAX];
double pre[MAX];

int max(int x, int y){
    return x > y ? x : y;
}
double min(double x, double y){
    return x>y?y:x;
}

int judge(double mid){
    for(int i = 1; i <= n; ++i){
        pre[i] = pre[i-1] + tr[i] - mid;
    }
    double minx = 0;
    for(int i = 0, j = m; j <= n; ++j, ++i){
        minx = min(minx, pre[i]);
        if(pre[j] - minx >= 0)return 1;
    }
    return 0;
}

int main(){
    scanf("%d%d", &n, &m);
    double l = 0, r = 0;
    for(int i = 1; i <= n; ++i){
        scanf("%lf",&tr[i]);
        if(r < tr[i])r = tr[i];
    }
    while(r-l>1e-8){
        double mid = (l + r) / 2;
        if(judge(mid))l = mid;
        else r = mid;
    }
    printf("%d\n", (int)(1000.0*r));
    return 0;
}