一次ac,真的好惊讶,凭着感觉做的,感觉贪心的话可以边写边思考
贪心策略:从最小开始贪心,对于小的直接吸纳且计算新的temp平均值

后面补上的证明,感觉非常不严谨,欢迎留言讨论!

性质分析——对于当前$a_i$

设$a_i$表示第i个人有的钱,$b_i$表示第i个人实际出的钱,sum表示实际要付的钱,$avg=\frac{s}{n}$
(1).$a_i>=avg$,$b_i=a_i$
证明:
$ans=\sqrt[]{\frac{\sum_{i=1}^{n}(b_i-avg)^2}{n}}$
设$x_i=b_i-avg,s=\sum_{i=1}^nx_i=0$,满足均值不等式的条件——“一正二定三相等”,$ans=\sqrt[]{\frac{\sum_{i=1}^nX_i^2}{n}}>=\frac{\sum_{i=1}^nx_i}{n}$,显然当$x_i=0,即b_i=a_i$时取得最小值
(2).$avg>a_i,b_i=a_i$
证明——反证法:
设当取到$a_i>b_i$时取得最小值,由于$\sum_{i=1}^nb_i=s$,有一个$a_i>b_i$,必然有一个或多个$b_i>a_i$,设a+b=s,显然对于$a^2+b^2$加上一个s不影响单调性,令$temp=2(a^2+b^2)-s^2=(a-b)^2$,显然a,b差值越小,temp的值越小，即$a_i取趋向于avg的数即可$,显然这与假设矛盾,原命题成立

贪心策略:先排好序,然后在”性质”的基础上,不断计算新的平均值

关键:对于每个b_i,我们后面的序列的$\sum_i^nx_i=\frac{s*n}{n+1}+(b_i-a_i)$——是一个定值,可以继续套用均值不等式求解
(1).$a_i>=avg$,直接取avg
(2).$a_i<avg,取a_i$

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

using namespace std;
typedef long long ll;

const int N=5e5+10;
int arr[N];

int main()
{
    int n,s;
    cin >> n >> s;
    for(int i=1;i<=n;i++){
        scanf("%d",&arr[i]);
    }
    sort(arr+1,arr+1+n);
    double avg=(double)s/n,temp=avg;
    //cout << avg << endl;
    double ans=0;
    for(int i=1;i<=n;i++){
        //cout << temp << ' ' << arr[i] << ' ' << ans << endl;
        if(arr[i]<temp){
            ans+=(avg-arr[i])*(avg-arr[i]);
            temp+=(temp-arr[i])/(n-i);
        }
        else{
            ans+=(avg-temp)*(avg-temp);
        }
    }
    ans=sqrt(ans/n);
    printf("%.4lf",ans);
    return 0;
}