| Time Limit: 1000MS | Memory Limit: 30000K | |
| Total Submissions: 14601 | Accepted: 4720 |
Description
FJ wants to build a fence around a contiguous group of these fields in order
to maximize the average number of cows per field within that block. The
block must contain at least F (1 <= F <= N) fields, where F given as input.
Calculate the fence placement that maximizes the average, given the
constraint.
Input
* Lines 2..N+1: Each line contains a single integer, the number of cows in a
field. Line 2 gives the number of cows in field 1,line 3 gives the number in
field 2, and so on.
Output
perform rounding, just print the integer that is 1000*ncows/nfields.
Sample Input
10 6
6
4
2
10
3
8
5
9
4
1
Sample Output
6500
Source
【题意】
给定一个正整数数列A，求一个平均数最大的、长度不小于L的子段。
【分析】
二分答案，判定是否存在一个长度不小于L的子段，平均数不小于二分的值。如果把数列中的每个数都减去二分的值，就转换为判定“是否存在一个长度不小于L的子段，子段和非负”。
<==>求一个子段，使得它的和最大，且子段的长度不小于L。
子段和可以转换为前缀和相减的形式，即设sumj表示Ai~Aj的和，
则有：max{A[j+1]+A[j+2].......A[i] } ( i-j>=L ) = max{ sum[i] - min{ sum[j] }(0<=j<=i-L) }（L<=i<=n）
仔细观察上面的式子可以发现，随着i的增长，j的取值范围 0~i-L 每次只会增大1。换言之，每次只会有一个新的取值进入 min{sumj} 的候选集合，所以我们没必要每次循环枚举j，只需要用一个变量记录当前的最小值，每次与新的取值 sum[i-L] 取min 就可以了。
【代码】
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+5;
int n,m;double a[N],b[N],sum[N];
double l,r,mid,eps=1e-6;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%lf",a+i),l=min(l,a[i]),r=max(r,a[i]);
while(r-l>eps){
mid=(l+r)/2;
for(int i=1;i<=n;i++) b[i]=a[i]-mid;
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+b[i];
double res=-1e10,mn=1e10;
for(int i=m;i<=n;i++){
mn=min(mn,sum[i-m]);
res=max(res,sum[i]-mn);
}
if(res>=0) l=mid;
else r=mid;
}
printf("%d\n",int(r*1000));
return 0;
}