最佳序列 题解

题目描述

你得到了一个 \(N\) 个非负整数组成的序列 \(A\)。

我们称由序列 \(A\) 的连续若干项组成的新序列为 \(A\) 的一个连续子序列。给出两个正整数 \(L,R(L \le R)\)。称 \(A\) 的每一个长度不小于 \(L\) 且不大于 \(R\) 的连续子序列为一个纯洁序列，定义纯洁度为纯洁序列的所有元素的平均值。

请你求出所有纯洁序列中的纯洁度的最大值。

输入格式

输入文件的第一行包括 \(3\) 个正整数 \(N,L,R\)。

第二行包括 \(N\) 个数，按顺序依次表示序列 \(A\) 的每一项。

输出格式

输出文件包括一行，一个实数，保留 \(4\) 位小数，表示答案。

样例

样例输入

3 2 3
6 2 8

样例输出

5.3333

数据范围与提示

对 \(10\%\) 的数据满足，\(1 \le N \le 200\)。

对 \(20\%\) 的数据满足，\(1 \le N \le 2000\)。

对 \(50\%\) 的数据满足，\(1 \le N \le 20000\)。

对 \(100\%\) 的数据满足，\(1 \le N \le 10^5, 1 \le L \le R \le N, 0 \le A_i \le 10^6\)。

分析

前缀和，然后暴力枚举所有合法区间的方法很容易想到，可以得 \(55\) 分。（要开 long long）

\(100\) 分做法：既然有最大值，说明如果平均超过最大值的区间是不存在的，而小于最大值的区间肯定存在，可以想到二分答案。

如何判断答案合法性呢？我们令 \(mid\) 为当前枚举的平均数，\(diff[i] = arr[i] - mid\)，那么只要存在长度在 \(L\) 到 \(R\) 之间的区间 \(diff[i]\) 总和大于等于 \(0\)，就说明是合法的；反之，若不存在，则说明当前的 \(mid\) 过大。

由于我们只需要找到任意一个 \(diff[i]\) 总和大于等于 \(0\) 的区间，我们可以用单调队列来维护，单调递增，然后找到一个合法区间即可。

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll maxn = 1e5 + 5;
ll n, L, R;
ll arr[maxn];

double diff[maxn], pre[maxn];
int que[maxn];
inline bool check(double mid) {
	for (int i = 1; i <= n; i++) {
		diff[i] = arr[i] - mid; // 求与当前二分的平均值的差
		pre[i] = pre[i - 1] + diff[i]; // 前缀和
	}
	int head = 1, tail = 0;
	double ans = -1e9;
	for (int i = L; i <= n; i++) { // 序列长度最短为 L，所以序列的末端从 L 开始
		while (head <= tail && pre[que[tail]] >= pre[i - L]) tail--;
		que[++tail] = i - L; // 维护单调递增的队列，队首的前缀和最小
		while (head <= tail && que[head] < i - R) head++; // 令区间长度超过 R 的出队
		if (head <= tail) ans = max(ans, pre[i] - pre[que[head]]); // 队首最小，这里 pre[i] - pre[que[head]] 就最大，我们只要找到一个 >= 0 的即可。
		if (ans >= 0.0) return true;
	}
	return false;
}

int main() {
	freopen("bestseq.in", "r", stdin);
	freopen("bestseq.out", "w", stdout);
	scanf("%lld%lld%lld", &n, &L, &R);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &arr[i]);
	}
	double l = 0, r = 1e8; // 实数二分
	while (r - l > 1e-7) {
		double mid = (l + r) / 2.0;
		if (check(mid)) l = mid;
		else r = mid;
	}
	printf("%.4lf", l);
	return 0;
}