自动搬运

查看原文

来自洛谷，原作者为

	CommandSR I love Segment Tree | FR'F R2U'R'U'RUR'F' RU'R'U'F'

搬运于2025-08-24 22:17:16，当前版本为作者最后更新于2025-08-12 08:21:06，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题意

link

题解

考虑对最优区间 $[l, r]$ 进行分讨。

1. 若 $L \leq r-l+1 \leq R$，则可以直接作为答案。
2. 若 $r-l+1 < L$，可以把它的长度补成 $L$。
3. 若 $r-l+1 > R$，无法补救，不能作为答案。

对于情况一，考虑分数规划，二分答案 $mid$。

$$\frac{M(l,r)-m(l,r)}{r-l+K} \ge mid$$ $$M(l,r)-m(l,r) \ge mid \cdot (r-l+K)$$

令 $a_r$ 为区间最大值，$a_l$ 为区间最小值。

$$(a_r-mid\cdot r) - (a_l-mid\cdot l) \ge mid\cdot K $$

令 $b_i = a_i-mid\cdot i$，$c_i = a_i+mid\cdot i$，分别跑一遍单调队列即可。

$a_l$ 为区间最小值，$a_r$ 为区间最大值同理。

对于情况二，直接跑单调队列，也要讨论 $a_l$ 为区间最小值，$a_r$ 为区间最大值，和 $a_r$ 为区间最小值，$a_l$ 为区间最大值的不同情况。

对于情况三，不会作为答案。

Code

// Problem: P6087
#include <bits/stdc++.h>
#define ll long long
#define db double
#define sz(x) (int)x.size()
#define F(i, a, b) for (int i = (a); i <= (b); ++i)
#define D(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std;
namespace IO {
#define typ ll
	inline typ rd() {
		typ x = 0; bool f = 1; char ch = getchar();
		while (ch < '0' || ch > '9') { if (ch == '-') f = 0; ch = getchar(); }
		while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
		return (f ? x : (-x));
	}
	inline void wr(typ x) {
		if (x < 0) putchar('-'), x = -x;
		if (x < 10) putchar(x+'0');
		else wr(x / 10), putchar(x%10+'0');
	}
}
using namespace IO;
const int N = 1e5 + 5;
const db eps = 1e-6;
int n, K, L, R, a[N], q[N], ff, ee;
db b[N], c[N];
db Sol1() {
	db ans = 0;
	ff = 1, ee = 0;
	F(i, 1, n) {
		while (ff <= ee && i - q[ff] + 1 > L) ++ff;
		if (ff <= ee) ans = max(ans, 1.0 * (a[i] - a[q[ff]]) / (L + K - 1));
		while (ff <= ee && a[q[ee]] >= a[i]) --ee;
		q[++ee] = i;
	}
	ff = 1, ee = 0;
	F(i, 1, n) {
		while (ff <= ee && i - q[ff] + 1 > L) ++ff;
		if (ff <= ee) ans = max(ans, 1.0 * (a[q[ff]] - a[i]) / (L + K - 1));
		while (ff <= ee && a[q[ee]] <= a[i]) --ee;
		q[++ee] = i;
	}
	return ans;
}
bool check(db x) {
	F(i, 1, n) b[i] = a[i] - x * i;
	ff = 1, ee = 0;
	F(i, 1, n) {
		while (ff <= ee && i - q[ff] + 1 > R) ++ff;
		if (ff <= ee && b[i] - b[q[ff]] - K * x >= 0) return 1;
		int j = i - L + 1;
		if (j > 0) {
			while (ff <= ee && b[q[ee]] >= b[j]) --ee;
			q[++ee] = j;
		}
	}
	F(i, 1, n) c[i] = a[i] + x * i;
	ff = 1, ee = 0;
	F(i, 1, n) {
		while (ff <= ee && i - q[ff] + 1 > R) ++ff;
		if (ff <= ee && c[q[ff]] - c[i] - K * x >= 0) return 1;
		int j = i - L + 1;
		if (j > 0) {
			while (ff <= ee && c[q[ee]] <= c[j]) --ee;
			q[++ee] = j;
		}
	}
	return 0;
}
db Sol2() {
	db l = 0, r = 1e4, mid;
	while (l + eps < r) {
		mid = (l + r) / 2;
		if (check(mid)) l = mid;
		else r = mid;
	}
	return l;
}
void GOGOGO() {
	n = rd(), K = rd(), L = rd(), R = rd();
	F(i, 1, n) a[i] = rd();
	cout << fixed <<setprecision(4) << max(Sol1(), Sol2()) << '\n';
}
int main() {
	int T = rd();
	F(gogo, 1, T) GOGOGO();
	return 0;
}