【题解】付账问题

账单计算

1. 初始时总账单除以人数即为每人应付钱数。
2. 但由于有人没有带够钱，无法支付自己应付的钱数，所以需要后续的人为其额外支付一部分钱。

计算过程

1. 将所有人所带钱数升序排序。
2. 计算每人 实付钱数 。如果所带钱数高于应付钱数，则实付钱数就是应付钱数。如果所带钱数不足以支付，则需要后续有人为其支付，为了使得标准差尽可能小，需要让更多的人分担这笔钱。

贪心 C++ 607ms

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <map>
#include <unordered_map>
#include <queue>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
#define x first
#define y second

const int N = 500010, M = N * 2;

int n;
LL sum;
// 带的钱
int a[N];
// 实付钱
long double b[N];

int main()
{
    cin >> n >> sum;
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

    sort(a + 1, a + n + 1);
    
    // t 表示每人应付钱数，但由于有人带不够，所以后面的人应付钱数会随之上升
    long double t = (long double)sum / n;
    for (int i = 1; i <= n; i ++ )
    {
        if (a[i] >= t) b[i] = t;
        else 
        {
            b[i] = a[i];
            // 由于第 i 个人带的钱不够支付应付钱数，所以需要后面的人来为其分担
            t += (t - a[i]) / (n - i);
        }
    }
    
    long double u = 0, avg = (long double)sum / n;
    for (int i = 1; i <= n; i ++ ) u += (b[i] - avg) * (b[i] - avg);
    printf("%.4Lf", sqrt(u / n));
    return 0;
}