文章目录

杂题 240201-2

发布于

题意

给定整数 $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';
}

暂无评论

发表评论