r

WA 两个点

用的单调队列写的 check

#include<bits/stdc++.h>
using namespace std;
const int N= 1e5+ 5;
const double eps= 1e-5;
int n, s, t, len, a[N];
double ans, sum[N], mn[N], q[N];
bool check(double x)
{
	int hh= 1, tt= 0;
	for(int i= 1; i<= n; i++) sum[i]= sum[i- 1]+ a[i]- x;
	for(int i= 0; i< len- 1; i++)
	{
		if(sum[i]<= q[tt] || tt< hh) q[++tt]= sum[i];
		if(q[tt]<= sum[i+ s]) return 1;
	}
	for(int i= len- 1; i+ s<= n; i++)
	{
		if(tt< ++hh) q[++tt]= sum[i];
		else if(sum[i]<= q[tt]) q[++tt]= sum[i];
		if(q[tt]<= sum[i+ s]) return 1;
	}
	return 0;
}
signed main()
{
	scanf("%d%d%d", &n, &s, &t);
	double l= 10005, r= -10005; len= t- s+ 1;
	for(int i= 1; i<= n; i++) scanf("%d", &a[i]), l= min(l, (double)a[i]), r= max(r, (double)a[i]);
	while(r- l> eps)
	{
		double mid= (l+ r)/ 2;
		if(check(mid)) ans= mid, l= mid;
		else r= mid;
	}
	printf("%.3lf", ans);
	return 0;
}