题目描述

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

/*
贪心：

容易想到的是 不够的尽量出，够的多出点。
但是，够的多出多少呢？ 我以为是和不够的那部分尽可能抵消。

事实上有更一般的解法：

首先，答案和次序无关，先排序；
如果不够，就尽量出，并且把 残差 转移到 剩下的人里。
如果够， 就除掉当前的平均值。

会不会有本来应该多出些，但是出少了的情况呢？

是不会的。排序之后，当前能出的钱数，后面也一定能出。那么后面这部分 相对于累加了残差后的s 均方差为0了。
而前面少的尽量出我们已经确定是 最优情况了。 所以能贪心得到全局的最优解。

类似于dp，通过每一步选取最优解得到全局最优解的情况。

*/


const int N = 500010;

int n;
int a[N];

int main()
{
    long double s;
    cin >> n >> s;
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    sort(a, a + n);

    long double res = 0, avg = s / n;
    for (int i = 0; i < n; i ++ )
    {
        double cur = s / (n - i);
        if (a[i] < cur) cur = a[i];
        res += (cur - avg) * (cur - avg);
        s -= cur;
    }

    printf("%.4Lf\n", sqrt(res / n));

    return 0;
}