题目描述
农夫约翰的农场由 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.整体思路:
该题使用二分法作答,乍一看很难联想到用二分,仔细分析发现 在区间答案一定在0~2000之中,且在该区间中有一部分大于等于答案,另一部分小于答案,这里就可以按照题中条件写出check()函数,当在N个田中找到一段连续长度不小于F且平均值大于mid的子区间,即满足check()函数,此时答案在右区间 l=mid;否则r=mid;二分枚举,不断缩小答案所在范围,最后找到为止!
2.check()函数如何设计?
核心是判断能否找到一个连续长度>=F且平均值>=mid的子块,这里使用前缀和思想,将将区间每块值减去mid,再求出s[i]前缀和,s[i] = s[i-1] + a[i] -mid;当s[j]-s[i-1]>=0;时说明能找出,答案>=mid;
要使其平均值最大,s[i-1]取s[i~1]中最小值minv;minv=min(minv,s[i]);
3. 浅谈二分思想:
核心是该问题是否满足二分性?即该区间中是否有一半元素满足条件,而另一半不满足条件,根据check()函数 判断选取左右区间,缩小答案范围,最终找出答案!
时间复杂度 O(nlogN)
参考文献
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5+7;
int n,F;
double a[N],s[N];
bool check(double x)
{
// 平均值的前缀和
for(int i=1;i<=n;i++) s[i] = s[i-1] + a[i] -x;
//若满足条件 s[j-i]>=0 即s[j] - min(s[i])>=0;
double minv = 0;
for(int i=0,j=F;j<=n;j++,i++)
{
minv = min(minv,s[i]);
if(s[j]-minv>=0) return true;
}
return false;
}
int main()
{
cin>>n>>F;
double l=0,r=0;
for(int i=1;i<=n;i++){
scanf("%lf",&a[i]);
r=max(r,a[i]);
}
while(r - l > 1e-5)
{
double mid =(l+r)/2;
if(check(mid)) // 能够找到一连续字段平均值>=mid
{
l=mid;
}
else r = mid;
}
printf("%d\n",(int)(r*1000));
return 0;
}