题目描述

Description

Farmer John’s farm consists of a long row of N (1 <= N <= 100,000)fields. Each field contains a certain number of cows, 1 <= ncows <= 2000.

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

Line 1: Two space-separated integers, N and F.

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

Line 1: A single integer that is 1000 times the maximal average.Do not 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

USACO 2003 March Green

解题方法：

要求连续找到至少K个数 是的该区间内平均值最大。

一开始想的是遍历至少含有K个数字的区间 记录哪个平均值最大。我需要使用三重循环，这样是不现实的。

思路：利用二分思想，求其前缀和。

利用空间换区时间的做法，我先找到最中间的

定位点即 mid

；并记录与mid 差值的平均值

对区间进行计算，保存最大值的情况

接着对区间进行选取，一开始我看被人代码的时候，我不理解为什么要选取最小项。后来想到是公式：

a[n] = s[n+1]-s[n]，所以当前面是最小的状态的时候后面的取的区间才会是最大的。

学习代码如下。

#include<iostream>
#include<cstring>
#include<algorithm>
#define maxn 3000
using namespace std;

int main(){
	int n,f;
	double l,s,mid;
	double a[200];
	double d[200];
	double sum[200]; 
	memset(a,0,sizeof(a));
	memset(d,0,sizeof(d));//记录平均数的差值； 
	memset(sum,0,sizeof(sum));
	l = 0; s = maxn;mid = 0 ;
	cin >> n >> f;
	for(int i = 1 ; i<= n ; ++i){
		cin >> a[i];
		l = max(l,a[i]);
		s = min(s,a[i]);
		//sum[i] = sum[i-1] + a[i];//计算前缀和 
	}
	
	while(l-s > 1e-4){
		mid = (l+s)/2;//是否为double？
		for(int i = 1 ; i <=n ;++i){
			d[i] = a[i] -mid;//计算差值 
		} 
		double max_sub_d = -1e9; double min_sub_d = 1e9;
		for(int i =1 ; i <= n ;++i){
			sum[i] = sum[i-1] +d[i];//与平均值的差值比较mid取得是否合适 
		}
		for(int i = f ; i <= n;++i){
			min_sub_d = min(min_sub_d,sum[i-f]); 
			max_sub_d = max(max_sub_d,sum[i]-min_sub_d);//算出最大k项至n中 最大的几项 
		} 
		if(max_sub_d >= 0) { //如果当前的平均值普遍偏大则扩大左极限范围 
			s = mid ;
		}
		else {//否则就缩小右极限 
			l = mid; //平均值是个基准数 
		}
		 
	}
	
	cout << int(l*1000) <<endl;
}

求其与平均数的差值，是在前缀和的基础上进行的改变。

当上下界限重合的时候就代表找到了。最终的这个位置就是所求得满足区间最大平均值的情况。、

涉及到的数学知识自己不是很有感觉。