P1404 平均数

和那道最小圈差不多。二分答案，前缀和判断即可。\(q_i-q_{i-m}>0\)代表能找到。

另外，这题有精度问题。

#include<bits/stdc++.h>
using namespace std;
int n,m;
long long a[100005];
long long q[100005];
bool check(long long w){
	long long Min=0x3f3f3f3f3f3f3f3f;
	for(int i=1;i<=n;i++)q[i]=q[i-1]+(a[i]-w);
	if(n==m)return q[n]>0;
	for(int i=m;i<=n;i++){
		Min=min(q[i-m],Min);
		if(q[i]-Min>0)return 1;
	}
	return 0;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i],a[i]*=10000000;
	long long l=-1145141919810,r=114514919810;//臭死了
	while(l<=r){
		long long mid=(l+r)/2;
		if(check(mid))l=mid+1;
		else r=mid-1;
	}
	printf("%d",(r+1)/10000);
	return 0;
} 

P1404 平均数

原文：https://www.cnblogs.com/kkksc0100/p/p1404-average_number.html