洛谷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\n", ans);

	return 0;

}
巴特西

洛谷P1419寻找段落

最新文章

热门文章
