模拟赛题讲解[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$ ，则
若 $a_n \gets a_n + nd(d > 0)$ ，则 $a’ = a+d$ ，并且
显然方差变大了，因此一个长度大于 $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;
}![模拟赛题讲解[29]](/medias/featureimages/p40.jpg)
![模拟赛题讲解[27]](/medias/featureimages/p212.jpg)