洛谷P1419寻找段落

题目

单调队列+前缀和

#include <bits/stdc++.h>
#define N 101001
using namespace std;
int n, s, t; int data[N];
double ans, temp[N], sum[N], l = -10000, r = 10000;
bool check(double a)
{
	 deque <int> q;
	memset(sum, 0, sizeof(sum));
	for (int i = 1; i <= n; i++)
		temp[i] = (double) data[i] - a;
	sum[0] = 0;
	for (int i = 1; i <= n; i++)
		sum[i] = sum[i - 1] + temp[i];
	for (int i = 1; i <= n; i++)
	{		   	 		
		if (i >= s) 
		{		 	 		
			while (q.size() && sum[i - s] < sum[q.back()])
				q.pop_back();	
			q.push_back(i - s);
		}		 
		if (q.size() && q.front() < i - t) 
		q.pop_front();
		if (q.size() && sum[i] >= sum[q.front()])	 
			return true;
	}			 
	return false;
} 				 
int main()		 
{				 
	scanf("%d%d%d", &n, &s, &t);
	for (int i = 1; i <= n; i++) scanf("%d", &data[i]);
	while (r - l > 0.00001)
	{			 
		double mid = (l + r) / 2;
		if (check(mid))
		ans = l = mid;
		else	 
		r = mid; 
	}
//	printf("%d", check(2));
    printf("%.3lf
", ans);
	return 0;	
}