题目描述

农夫约翰的农场由 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)$

在做的时候就知道算法超时了,为了检验算法的正确性,还是写了一下
在n不超时的情况下跑出来的数据都是对

后枚举所有可能的圈法算出平均值,
平均值是利用前缀和来快速求解

C++ 代码

#include<iostream>
#include <math.h>

using namespace std;
float a[100010];
float ping;
float eps=1e-3;
int main()
{
    int N,F;
    cin>>N>>F;
    a[0]=0;
    for(int i=1;i<=N;i++)
    {
        cin>>a[i];
        a[i]+=a[i-1];
    }
    float res=0;
    for(int i=F;i<=N;i++)
    {
        for(int j=i;j<=N;j++)
        {
            ping=(a[j]-a[j-i])/i*1.0;
            if(ping-res>eps)
                res=ping;
        }
    }
    cout<<int(res*1000);
}

算法2

(二分转化思考方式)

问题转化:最大平均值——>存在是否有一段大于等于F的子序列的值大于等于给定平均值,给定平均值通过二分搜索确定
平均值的技巧:所有数减去给定平均值,如果子序列大于等于给定平均值,那么子序列的和会大于0
双指针:每次j+1相当于加入了一个元素i+1进入待判定序列,就需要更新最小值

该题要求求最大的平均值,由于存在多种情况,且每种情况比较复杂,所以很难直接求出,考虑怎么转化为判定问题
可以抓化成,枚举一定范围内的所有平均值,看该种平均值在 圈大于等于F块地 能否达到

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;

int a[N];
double sum[N];
int n,f;

bool check(double avr)
{
    for(int i=1;i<=n;i++)
        sum[i]=sum[i-1]+a[i]-avr;
    double minv=0;
    for(int i=0,j=m;j<=n;j++,i++)
    {
        minv=min(sum[i],minv);
        if(sum[j]>minv) return true;
    }
    return false;
}
int main()
{
    cin>>n>>f;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    double l =0;
    double r=2000;
    while(r-l>1e-3) //实数的二分法
    {
        double mid=(l+r)/2;
        if(check(mid))  l=mid;  //该数字可以满足,就可以看更大的数字能否满足所以移动左边界
        else r=mid;
    }
    cout<<int(r*1000);
}