模拟赛题讲解[28]

来自 s_r_f 2023-08-03 noi.ac #3196

题目描述:

定义函数 \(f(S) = \dfrac{1}{|S|}\sum\limits_{x\in S} x\)，即可重集 \(S\) 的均值；

\(g(S) = \dfrac{1}{|S|}\sum\limits_{x\in S} (x-f(S))^2\)，即可重集 \(S\) 的方差。

小 B 有一个大小为 \(n\) 的可重整数集 \(S = \{a_1,a_2,\cdots ,a_n\}\).

小 B 想知道，从 \(S\) 中任选一个子集 \(T\) 满足 \(L \leq |T| \leq R\)，最小的 \(g(T)\) 的值。

输入格式：

第一行，三个整数 \(n\) \(L\) \(R\)

第二行，\(n\) 个整数 \(a_1,\cdots a_n\)

输出格式：

一行一个实数表示答案。

答案的相对误差或绝对误差不超过 \(10^{-6}\) 会被判为正确答案。

输入样例1：

5 3 4
2 12 9 8 4

输出样例2：

2.8888888889

数据范围：

子任务 1(10pts) : \(n \leq 20\)

子任务 2(20pts) : \(n \leq 2000\)

子任务 3(20pts) \(:\) \(R-L \leq 10\)

子任务 4(50pts) : \(1 \leq n \leq 2 \times 10^5,1 \leq L \leq R \leq n,0 \leq a_i \leq 10^{3}\)

提示：一部分写法可能需要用到 long double。但在正式比赛时谨慎使用。

题解：

说好的难度 ABCD ，结果我只会 AD （哭哭

一个常见的 trick 是，选方差尽可能小的集合，一定是排序后的一个区间。

我们考察一个长为 \(L\) 区间，在加入一个更大的元素后，对方差的影响。

不妨设 \(a_1<a_2< \dots<a_n,~ a=\frac{1}{n} \sum a_i\) ，则 \[ \sigma=\frac{1}{n} \sum\left(a_i-a\right)^2=\frac{1}{n} \sum a_i^2-a^2 \] 若 \(a_n \gets a_n + nd(d > 0)\) ，则 \(a' = a+d\) ，并且 \[ \begin{aligned} \sigma^{\prime} & =\left(\frac{1}{n} \sum a_i^2\right)+n d^2+2 d a_n-\left(a^2+d^2+2 a d\right) \\ & =\sigma+(n-1) d^2+2 d\left(a_n-a\right) \end{aligned} \] 显然方差变大了，因此一个长度大于 \(L\) 的区间是不优的，即 \(R\) 在本题中毫无意义。

所以我们只需要算个方差就好啦！

时间复杂度 \(\mathcal{O}(n \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(double &x,double y) { x > y ? x = y : 0; }
#define N ((int)(2e5 + 15))

int n,L,R,a[N],b[N],c[N]; double res = 1e18;
double calc(int l,int r)
{
    double p = ((double)b[r] - b[l - 1]) / (r - l + 1);
    return (((double)c[r] - c[l - 1]) - ((double)r - l + 1) * p * p) / (r - l + 1);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> L >> R;
    for(int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n);
    for(int i = 1; i <= n; i++) {
        b[i] = b[i - 1] + a[i], c[i] = c[i - 1] + a[i] * a[i];
    }
    for(int i = 1; i + L - 1 <= n; i++) down(res, calc(i, i + L - 1));
    cout << fixed << setprecision(10) << res << '\n';    
    return 0;
}