Best Cow Fences POJ - 2018 (二分答案)

                                                    Best Cow Fences 

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

题意: 给定一个正整数数列A , 求一个平均数最大,长度不小于 L 的字段 . 

 二分答案, 判定" 是否存在一个长度不小于L的字段 ,平均数不小于二分的值 "

如果把数列中 的每个数都减去二分的值,就转化成 判定" 是否存在一个长度不小于 L 的子段 ,子段和非负" . 

子段和可以转化为前缀和相减的形式 , 即 sum [i] 表示 A[1] ~ A[i] 的和 , 则有  : max{ A[j+1] + A[j+2] , ....A[i] }( i -j >=L) = max( sum[i ] - min(sum[j] ) (0<=j<= i -L >) }  

为甚么它符合二分的单调性呢? 对于二分模型,我们把问题装换成函数问题, 在该题中其定义域就是平均值,值域就是去掉平均值后的子序列的和, 可以把该题看成  随自变量x 的值越大,平均值越大, 分界点左边不合法,右边合法 . 

  

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <set>
#include <cstring>
#include <stack>
#include <set>
#include <vector>
#include <queue>
#define Swap(a,b)  a ^= b ^= a ^= b
#define pi acos(-1)
#define cl(a,b) memset(a,b,sizeof(a))
using namespace std ;
typedef long long LL;
//const int N = 1e7+10 ;
const int inf = 0x3f3f3f3f;
const int MAX = 1e5+5;
double a[MAX] ;
double sum[MAX] ;

int main()
{
	int n , f ;
	double l = -1e6 , r = 1e6 ;
	cin >> n >> f ;

	for(int i = 1 ; i<=n ; i++){
		scanf("%lf",&a[i]);
	
	}
	double eps = 1e-5 ;

	while(r-l > eps){
		double mid = (l+r)/2 ;
		
		for(int i = 1 ; i<=n ; i++){
			// 前缀和
			sum[i] = sum[i-1] + a[i]-mid ;
		}
		double ans = -1e10;
		double minn = 1e10 ;
		for(int i = f ; i <=n ; i++){
			minn = min(minn,sum[i-f]) ;
			ans = max(ans,sum[i]-minn) ; // 大于等于 L长度 的子序列的和,每次都取最大,单调增
		}
		if(ans >=0 ){
			l = mid ;
		}
		else{
			r = mid ;
		}
	}
	printf("%d\n",int(r*1000));
	return 0 ;
}