YbjOJ 最大均值

给定正整数序列A ，求一个平均数最大的，长度不小于 L 的（连续的）子段。 

题目描述很简单，一道二分题，需要注意细节和check函数的写法

首先是二分，一个版子（在实数范围内并且有精读问题）

while(l+eps < r){
	double mid = (l+r) / 2;
	if(check(mid)) l=mid;
	else r=mid;
}

然后就是check函数

如果把序列里的数都减去二分的值，问题就变成”是否存在一个长度不小于L的子段，子段和非负

子段和可以转化为前缀和的问题，每次j的取值都会增加一，所以用一个变量记录最小值，取min就可以

bool check(double num){
	for(register int i(1) ; i<=n ; i=-~i) b[i] = a[i] - num;
	for(register int i(1) ; i<=n ; i=-~i) sum[i] = sum[i-1] + b[i]; //前缀和
	double ans = -1e10,minn = 1e10;
	for(register int i=L ; i<=n ; i=-~i){
		minn = min(minn,sum[i-L]);
		ans = max(ans,sum[i] - minn);
	}
	return ans>=0;
}

然后这道题就可以安心二分了，别忘了最后的精读问题

#include
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-48 ; ch=getchar();}
	return x*f;
}
int n,L;
double a[100010],b[100010],sum[100010];
bool check(double num){
	for(register int i(1) ; i<=n ; i=-~i) b[i] = a[i] - num;
	for(register int i(1) ; i<=n ; i=-~i) sum[i] = sum[i-1] + b[i];
	double ans = -1e10,minn = 1e10;
	for(register int i=L ; i<=n ; i=-~i){
		minn = min(minn,sum[i-L]);
		ans = max(ans,sum[i] - minn);
	}
	return ans>=0;
}
int main(){
	cin >> n >> L;
	for(register int i(1) ; i<=n ; i=-~i) cin >> a[i];	
	double l=-1e6,r=1e6;
	double eps = 1e-5;
	while(l+eps < r){
		double mid = (l+r) / 2;
		if(check(mid)) l=mid;
		else r=mid;
	}
	cout << int(r*1000);
	return 0;
}