题意
给定整数 $n, L, R$，长度都为 $n$ 的数组 $a$ 和 $b$。选择一段长度在 $\left[L, R\right]$ 的区间，使得 $\dfrac{\sum a}{\sum b}$ 最大，求最大值。
$1 \leq n \leq 10^5$
题解
好像是个经典的 01 分数规划。首先二分 $x$，现在要检查是否有一段区间的 $\dfrac{\sum a}{\sum b} \geq x$，即 $\sum a \geq x \sum b$，即 $\sum a - x \sum b \geq 0$，我们新建一个数组 $c_i = a_i - xb_i$，这样我们只需要检查是否有 $c_r - c_{l - 1} \geq 0$ 即可（其中 $L \leq r - l + 1 \leq R$），使用一个数据结构维护区间最小值即可。
代码
struct Compare {
double operator()(double a, double b) { return min(a, b); }
};
void STRUGGLING([[maybe_unused]] unsigned TEST_NUMBER) {
tp n, L, R; bin >> n >> L >> R;
vector<tp> a(n + 1), b(n + 1);
bin.rar(1 + FULL(a)); bin.rar(1 + FULL(b));
auto check = [&](double c) -> bool {
vector<double> t(n + 1, 0);
for (tp i = 1; i <= n; ++i) t[i] = a[i] - c * b[i] + t[i - 1];
lib::ST<double, Compare> rmq(t);
for (tp i = 1; i <= n; ++i) {
tp r = i - L, l = max(ZERO, i - R);
if (r < 0) continue;
if (t[i] >= rmq(l, r)) return true;
}
return false;
};
double l = -1e9, r = 1e9;
while (r - l >= 1e-7) {
double mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid;
}
bin.precision(7);
bin << l << '\n';
}