题目描述

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

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

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

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

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

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

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

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

样例

输入样例

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

输出样例

6500

算法1

(暴力枚举) $O(n^2左右)$

不是真正的暴力枚举！

是加了前缀和的暴力枚举……

就是枚举每个区间

TLE可能迟到，却从不缺席

时间复杂度

$O(n^2)$左右

C++ 代码

#include<iostream>
using namespace std;
int A[100005];
int main(){
    int n,f;
    double ans=0;
    scanf("%d%d",&n,&f);
    for(int i=1;i<=n;i++){
        scanf("%d",&A[i]);
        A[i]+=A[i-1];   //求前缀和
    }
    for(int len=f;len<=n;len++)     //枚举区间长度
        for(int i=0,j=i+len;j<=n;i++,j++)   //枚举区间开头，根据长度得到结尾
            ans=max(ans,double(A[j]-A[i])/len);
    printf("%d",int(ans*1000));
}

算法2

(二分答案) $O(n\,log牛数最大值)左右$

话说这道题好像看着跟二分没啥关系

但其实就是二分答案

就是二分出区间的最大平均值可能是多少

很明显，这个答案最小不可能小于0

最大其实不可能超过牛最多的那块田地里的牛数

（毕竟如果不选人家自己，连这个数都不太可能到达）

有的人也许懒得算牛数最多的那块田地里的牛数，

但懒人也有懒人的办法：

题目中说每块田牛数不超过2000，二分右端点就设置成2000

这种做法其实在计算较小数据时真的很费

（这题的数据又不那么强）

所以还是比先前说的求最大值慢一点的

本人闲的没事测了一下，就是124ms和143ms的区别

那么怎么判定一种答案是否合法呢？

我们写一个O(n)的判定函数

首先我们枚举到了整数x，

在求前缀和的时候每位减掉一个x

那么前缀和数组的每位就会代表数组前缀的平均值减去x。

设置并维护一个当前最小位

如果当前位大于这个最小位

就说明肯定存在一个区间可以满足平均值大于现在二分到的答案

（具体来说就是当前位减去最小位这个区间）

所以

（先不考虑这个答案存不存在）当前答案是合法的

这样，答案就会越来越接近正确答案

因为只有当答案不合法，r才会被更新

所以最后r这个答案一定是合法的

而且r一定大于l

说不定正好卡在整数两边

输出l*1000会下取整而比正确答案小1

所以输出r*1000

时间复杂度

$O(n\,log牛数最大值)左右$

C++ 代码

#include<iostream>
using namespace std;
const int N=100005;
int f,n,A[N];
double s[N];
bool check(double now){
    double minn=0;
    for(int i=1;i<=n;i++)
        s[i]=s[i-1]+A[i]-now;
    for(int i=f;i<=n;i++){
        minn=min(minn,s[i-f]);
        if(s[i]>=minn)
            return true;
    }
    return false;
}
int main(){
    scanf("%d%d",&n,&f);
    double l=0,r=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&A[i]);
        r=max(r,(double)A[i]);
    }
    while(r-l>1e-5){
        double mid=(l+r)/2;
        if(check(mid))
            l=mid;
        else
            r=mid;
    }
    printf("%d",int(r*1000));
}