贪心策略:
先排序,按平均值来作为标准从小到大遍历所有人的钱数
- 小于均值的,直接全掏,不够的改变平均值让后面的人均摊
- 大于均值的,直接按均值掏即可
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#define N 500010
using namespace std;
int n;
int q[N];
int main()
{
double s;
scanf("%d %lf",&n,&s);
for(int i = 0;i < n;i ++) scanf("%d",&q[i]);
sort(q,q+n);
double res = 0,avg = s / n;
for(int i = 0;i < n;i ++)
{
double cur = s / (n - i);
if(q[i] < cur) cur = q[i];
res += (cur - avg) * (cur - avg);
s -= cur;
}
printf("%.4lf\n",sqrt(res/n));
return 0;
}