Best Cow Fences(求长度不小于f的连续子串的平均值的最大值)

Best Cow Fences

时间限制: 1 Sec  内存限制: 128 MB

题目描述

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. 

输入

* 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. 

输出

* 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. 

样例输入

复制样例数据

10 6
6 
4
2
10
3
8
5
9
4
1

样例输出

6500

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

const double eps = 1e-6;
int n, f;
double a[100005], sum[100005], maxx[100005], b[100005];

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%d %d", &n, &f);
	double l = 2005.0, r = 0;
	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){
		double mid = (r + l) / 2;//二分平均值
		sum[0] = 0, maxx[0] = 0;
		for (int i = 1; i <= n; i++){
			b[i] = a[i] - mid;//b[i]表示减去平均值后的a[i]
			sum[i] = sum[i - 1] + b[i];//前缀和
			maxx[i] = max(b[i], maxx[i - 1] + b[i]);//到第i项时，前面的最大连续和
		}
		double t = sum[f];//t用来判断是否存在有大于等于f的连续子串可以平均分mid
		for (int i = f + 1; i <= n; i++){
			if(maxx[i - f + 1] + sum[i] - sum[i - f + 1] > t){//判断长度为(f+(i-f+1)前面的最大可选长度)的最大值
				t = maxx[i - f + 1] + sum[i] - sum[i - f + 1];
			}
		}
		if(t < 0) r = mid;//如果<0说明平均值过大
		else l = mid;
	}
	int ans = r * 1000;
	printf("%d\n", ans);

	return 0;
}
/**/