题目描述

关系

内容

几个人一起出去吃饭是常有的事。

但在结帐的时候，常常会出现一些争执。

现在有 n $n$ 个人出去吃饭，他们总共消费了 S $S$ 元。

其中第 i $i$ 个人带了 ai $a_i$ 元。

幸运的是，所有人带的钱的总数是足够付账的，但现在问题来了：每个人分别要出多少钱呢？

为了公平起见，我们希望在总付钱量恰好为 S $S$ 的前提下，最后每个人付的钱的标准差最小。

这里我们约定，每个人支付的钱数可以是任意非负实数，即可以不是 1 $1$ 分钱的整数倍。

你需要输出最小的标准差是多少。

标准差的介绍：标准差是多个数与它们平均数差值的平方平均数，一般用于刻画这些数之间的“偏差有多大”。

形式化地说，设第 i $i$ 个人付的钱为 bi $b_i$ 元，那么标准差为 :

输入格式

第一行包含两个整数 n、S $n、S$；

第二行包含 n $n$ 个非负整数 a 1, …, an $a_1, \dots , a_n$。

输出格式

输出最小的标准差，四舍五入保留 4 $4$ 位小数。

数据范围

1≤n≤5×105 $1\le n\le 5\times {10}^5$,
0≤ai≤109 $0\le a_i\le {10}^9$,
0≤S≤1015 $0\le S\le {10}^{15}$。

输入样例 1：

5 2333
666 666 666 666 666

输出样例 1：

0.0000

输入样例 2：

10 30
2 1 4 7 4 8 3 6 4 7

输出样例 2：

0.7928

问题分析

最初思路

思路分析

设每个人平均需要支付的钱数为 ${\displaystyle x}$，我们的目的是让每个人支付的钱数都尽可能靠近这个 x，具体来说，那么：

1. 对于拥有钱数低于 x 的人，需要把自己所有的钱都拿出去来减小与平均值 x 的差距；
2. 对于钱数大于 x 的人，只需要支付平均值就可以了；

但是，一个人少付了钱，那么总有人需要多付的？谁来多付呢？平摊。即我们可以重新计算平均值。例如假如第一个人的钱少于平均值，那么当这个人付完钱后，第二个以及之后的人就需要支付这些钱。

程序的贪心策略是这样的：

1. 计算出所有人应该支付的平均金额。
2. 将所有人拥有的钱从小到大排序。
3. 从最少的钱开始，如果这个人拥有的钱少于平均值，那么他就支付所有他拥有的钱。
4. 然后重新计算剩下的人的新平均值。
5. 如果下一个人的钱也少于新的平均值，那么他也支付所有他拥有的钱，再次更新剩下的人的平均值。
6. 重复这个过程，直到所有人都支付了钱。

执行流程设计

总结

代码实现

#include <bits/stdc++.h>
using namespace std;

#define double long double

const int N = 5e5 + 10, eps = 1e-8;
int n; double s;
int a[N]; double b[N];

int main()
{
    scanf("%d%llf", &n, &s);
    
    for (int i = 0; i < n; i++) {scanf("%d", &a[i]);}
    
    sort(a, a + n);
    
    double cur_avg = 1.0 * s / n, sum_b = 0; 
    double mius = eps;
    for (int i = 0; i < n; i++) {
        cur_avg = 1.0 * s / (n - i);
        
        if (a[i] <= cur_avg) {
            b[i] = a[i];
        } else {
            b[i] = cur_avg;
        }
        
        sum_b += b[i];
        s -= b[i];
    }
    
    double avg_b = sum_b / n, tmp = 0;
    for (int i = 0; i < n; i++) {
        tmp += (b[i] - avg_b) * (b[i] - avg_b);
    }
    
    double res = sqrt(tmp / n);
    printf("%.4llf", res);
    return 0;
}