题意
给定 $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() {
}