文章目录

杂题 240201-1

发布于

题意

给定 $n, L, R$ 和一个长度为 $n$ 的数组 $a$,要求选出 $L$ 到 $R$ 个数,使得选出的数组成的可重集的方差最小。

$1 \leq n \leq 2 \times 10^5, a_i \leq 10^3$

题解

可以先将 $a$ 排序。

众所周知,方差是用来衡量混乱程度的。我们选的数一定是排序后数组的一段区间。这时你会发现这段区间长度越小,越容易构成较小的方差。也就是说我们选出的一定是 $L$ 个数。

然后 $\mathcal O \left(n\right)$ 求答案。

代码

tp op(tp a, tp b) { return a + b; }
tp e() { return 0; }

void STRUGGLING([[maybe_unused]] unsigned TEST_NUMBER) {
  tp n, l, r; bin >> n >> l >> r;
  double tar = INF;
  vector<tp> a(n), b(n);
  bin.rar(FULL(a));
  stable_sort(FULL(a));
  for (tp i = 0; i < n; ++i) b[i] = a[i] * a[i];
  lib::Light_Segtree<tp, op, e> te(a), ge(b);
  for (tp i = 0; i + l <= n; ++i) {
    tp a = i, b = i + l - 1;
    tp c = ge.product(a, b), d = te.product(a, b);
    dbg(a, b, c, d);
    tar = min(tar, (c - 2. * d * d / l) / l + d * d * 1. / l / l);
  }
  bin.precision(12);
  bin << tar << '\n';
}

void MIST() {
}

暂无评论

发表评论