题目描述

有n个牛栏，从左到右连续一排，编号为1~n, 每个牛栏有一个高度ai。现在BSNY想从中找连续的一些牛栏，牛栏个数至少为L，他想知道，平均高度最大是多少。

输入

第一行输入n, L
接下来n行每行输入ai

输出

输出答案最大平均高度，具体的说为 (高度和/数量)*1000（结果直接舍掉小数，输出整数部分）

样例输入

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

样例输出

6500

提示

1<=n<=100000, 1<=ai<=2000 1<=L<=n

思路

可能的答案不大,且符合单调性,可以采用二分答案
每次获得一个可能的mid,数组中每一个值减去mid,进行统计,只需有>=Len的一段之和>=0即可成为答案,用前缀和优化求和过程
可以用last变量记录前面出现的最小值,O(n)扫一遍即可
注意精度问题,可以用Double类型,或者干脆直接*1000,Long long

代码

#include <bits/stdc++.h>
using namespace std;

int mt,a[100005],n,len,ans;
long long tmp[100005];
int main(){
    cin>>n>>len;
    for (int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        a[i]*=1000;
        mt=max(mt,a[i]);
    }
    int l=0,r=mt,mid;
    while (l<=r){
        int last=0,y=0;
        mid=(l+r)/2;
        for (int i=1;i<=n;++i) tmp[i]=a[i]-mid;
        for (int i=1;i<=n;++i) tmp[i]+=tmp[i-1];
        for (int i=len;i<=n;++i){
            if (tmp[i-len]<tmp[last]) last=i-len;
            if (tmp[i]-tmp[last]>=0){
                y=1;
                break;
            }
        }
        if (y){
            ans=mid;
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    cout<<ans<<endl;
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/45/