题目描述
农夫约翰的农场由 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
算法
(化整+二分答案)
该方法避免了浮点数精度问题,直接化整后用实数二分即可。具体看代码注释~~~
C++ 代码
#include<bits/stdc++.h>
using namespace std;
long long n,m;
long long sum[1000005];//记录前缀和
long long a[1000005];//记录数组
bool check(int x)
{
long long Min=999999999;//设置最小值,从i-m中找到最小的
for(int i=1;i<=n;i++)
{
sum[i]=sum[i-1]+a[i]-x;//求出前缀和的平均数,利用x,相当于每个数减去平均值再进行累加
//cout<<sum[i]<<endl;
if(i>=m)//当数的个数大于m,即长度大于题目所要求的m时,进入该分支
{
Min=min(Min,sum[i-m]);//找到前面搜索到的最小前缀平均和
if(sum[i]-Min>=0)//如果存在前缀和大于这个最小值,即这个x小了,可以更大,所以返回true
return true;
}
}
return false;//找不到,返回false
}
int main()
{
cin>>n>>m;
long long Max=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[i]=a[i]*10000;//转化为整数
Max=max(a[i],Max);//找到二分右区间最大值,一群数平均数不可能大于最大的那个数
//cout<<Max<<endl;
}
int l=0,r=Max;
while(l<r)//二分操作
{
int mid=(l+r+1)/2;
if(check(mid))
{
//ans=mid;
l=mid;
}
else
r=mid-1;
}
printf("%d\n",l/10);
return 0;
}