自动搬运

查看原文

来自洛谷，原作者为

	Pengzt 自己选择的路，跪着也要走完。

搬运于2025-08-24 22:33:10，当前版本为作者最后更新于2023-02-15 21:58:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P7795

简单二分。

显然 $\mathcal{O}(n ^ 2)$ 的时间复杂度无法通过。

使子段平均值最大，考虑二分。

可以二分平均值 $mid$，然后判断是否有满足条件的和 $\ge 0$ 且长度 $\ge k$ 的子段。

记录一个前缀和数组 $s$，变为对于每个 $i$，看是否存在 $j(j<i)$ 使得 $i-j\ge k$ 且 $s_i\ge s_j$。这个东西显然可以变为查询 $s$ 的某一个前缀中是否存在一个值使得 $s_j<s_i$，从前往后扫一遍做一个前缀 $\min$ 即可。

时间复杂度：$\mathcal{O}(\dfrac{n\log V}{\text{eps}})$，其中 $\text{eps}$ 为设置的精度，$V$ 为值域。

代码：

#include<bits/stdc++.h>

using ll = long long;
using pii = std::pair<int, int>;

const int N = 3e5 + 5;
const double eps = 1e-6;
int n, k;
int a[N];
double b[N];

bool check(double mid) {
	for (int i = 1; i <= n; i++) {
		b[i] = b[i - 1] + a[i] - mid;
	}
	double res = -1, mnv = 1e9;
	for (int i = k; i <= n; i++) {
		mnv = std::min(mnv, b[i - k]);
		res = std::max(res, b[i] - mnv);
	}
	return res >= 0;
}

int main() {
	scanf("%d %d", &n, &k);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	double l = 1, r = 1e6;
	while (l + eps < r) {
		double mid = (l + r) / 2;
		if (check(mid))
			l = mid;
		else
			r = mid;
	}
	printf("%.6lf\n", l);
	return 0;
}