题目描述
几个人一起出去吃饭是常有的事。但在结帐的时候，常常会出现一些争执。

现在有 n 个人出去吃饭，他们总共消费了 S 元。其中第 i 个人带了 a_i 元。幸运的是，所有人带的钱的总数是足够付账的，但现在问题来了：每个人分别要出多少钱呢？

为了公平起见，我们希望在总付钱量恰好为 S 的前提下，最后每个人付的钱的标准差最小。这里我们约定，每个人支付的钱数可以是任意非负实数，即可以不是 1 分钱的整数倍。你需要输出最小的标准差是多少。

标准差的介绍：标准差是多个数与它们平均数差值的平方平均数，一般用于刻画这些数之间的 “偏差有多大”。形式化地说，设第 i 个人付的钱为 b_i 元，那么标准差为：
\sigma = \sqrt { \frac {1}{n} \sum_{i=1}^{n} \left ( b_i - \frac {1}{n}\sum_{i=1}^{n} b_i \right)^2 }

输入描述
第一行包含两个整数 n、S；
第二行包含 n 个非负整数 a1~an。

其中，
n \le 5\times 10^5,\quad 0\le a_i \le 10^9

输出描述
输出最小的标准差，四舍五入保留 4 位小数。
保证正确答案在加上或减去 10^{-9}后不会导致四舍五入的结果发生变化。

这道题使用了贪心算法

贪心算法 : 不考虑长远，不枚举全部方案，不回溯，只看当前最优的选择，直接默认了当前最优的选择是全局最优的选择，就像在1元，5元，10元中拿固定数量的钱一样，人的贪心心理会全拿10元的钱币而不是全拿1元的钱币。

这道题，要在消费S元以及每个人带的钱的数量不同的前提下，让i个人用最公平的方式来出钱，也就是实现标准差最小化

最公平的方式，我们首先想到的是求平均数，让每个人都付平均数的钱，这样子无疑是最公平的，但是要知道，每个人带的钱的数量都不一致，有的人带的少，有的人带的多，带的多的注定要多出一点，而带的少也必须全部出完，这才能达到相对公平的状态

我们不妨以平均线为分界线，如果一个人的钱总是高于平均线以上的人称为富人，他们要出比平均线更多的钱，如果一个人的钱总是低于平均线以下的人称为穷人，他们必须全部出完

当我们区分好之后，首先要做的是排序，把穷人放在前面，富人放在后面，下面先对穷人进行处理

这里我们会使用到动态平均值的方法，为什么会用到动态平均值，看下面的一个例子

假设有三个人吃饭，总额为12块钱，a有3元，b有7元，c有9元

平均每个人应该要出12/3=4元，而a的钱不够，那他只能把身上的钱全出了，那就是还剩下9元，平均值为9/2=4.5，b出4.5元，c出4.5元

如果不采用动态平均值，那么a出3元，按照平均值，b只需要出4元，那么c要出5元，这显然是不公平的，所以说我们需要使用动态平均值来让后面富人出的每一笔钱都足够接近，足够公平

使用动态平均值，就注定了穷人和富人在一开始是无法直接确定的，在处理穷人的时候，他们的钱总是低于平均值，然后计算下一个平均值的时候，会发现下一个平均值会比上一个平均值高，就这样不断遍历每个穷人，直到有一个人，他的钱是大于平均值的，这里也隐含着在他之后的每一个人带的钱都会大于平均值，这时候我们不必使用动态平均值，因为后半部分的人的钱全部花出去后会拉低平均值，导致越往后花的钱越少，这显然是不公平的，所以说对于富人，我们采取的是先计算统一的一个平均值，然后让这些富人支付平均值的钱，这样子就达到了相对公平的境界。

综上，我们写代码的思路为：把低于动态平均值的人的钱全部花完，如果有些人的钱一直大于动态平均值，那么我们先处理好穷人的钱，然后计算出去掉穷人的平均值，再让富人花费这个平均值的钱

具体C语言代码展示：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

long long int list[500000];   //放在静态区域，防止栈溢出
double rich[500000];         //记录富人花钱的
double poor[500000];         //记录穷人花钱的

int main(void)
{
    long long int price, n, i = 1;
    double aver;
    scanf("%lld %lld", &n, &price);

    for (i = 0; i < n; i++)
    {
        scanf("%lld", &list[i]);
    }

    // ==========【这里提前放选择排序！！贪心必须先排序】==========
    long long min_location, x, y, temp;
    for (x = 0; x < n - 1; x++)   //选择排序 ，从小到大
    {
        min_location = x;
        for (y = x + 1; y < n; y++)
        {
            if (list[y] < list[min_location])
            {
                min_location = y;
            }
        }
        temp = list[min_location];
        list[min_location] = list[x];
        list[x] = temp;
    }
    // =================================================================

    const double FIRST_AVER = 1.0 * price / n;   //先保留一开始的平均值和人数
    const long long int N = n;
    double remain_sum = 1.0 * price;             //剩余账单改成double，存小数
    int remain_cnt = n;                          //剩余人数

    for (i = 0; i < N; i++)   //【修改】原来list[i]!=0是错的，改成遍历全部原始人
    {
        aver = remain_sum / remain_cnt;    //每次重新计算当前动态平均值
        if (list[i] < aver)                //如果一个人带的钱少于平均值，那他得出他身上的全部钱
        {
            remain_sum -= list[i];
            poor[i] = list[i];              //把他花的钱存起来
            list[i] = 0;                    //标记为穷人
            remain_cnt -= 1;
        }
        else
        {
            //剩下所有人统一出aver，直接赋值rich数组
            int j;
            for (j = i; j < N; j++)
            {
                rich[j] = aver;
                list[j] = -1; //标记这部分是富人
            }
            break;
        }
    }

    //开始计算方差
    double sumOfai = 0.0, result;
    for (i = 0; i < N; i++)  //【修改！不要循环到500000，只循环真实人数N】
    {
        double bi;
        if (list[i] == 0)
        {
            bi = poor[i];
        }
        else
        {
            bi = rich[i];
        }
        double diff = bi - FIRST_AVER;
        sumOfai += diff * diff;
    }
    sumOfai = sumOfai / N;
    result = sqrt(sumOfai); //求标准差
    printf("%.4lf", result);

    return 0;
}