分析
这题一看就是贪心（废话）， 那么怎么个贪心法呢？首先我们要知道标准差表示的是数据的波动程度，其值越大波动越大。要使得标准差小，我们就要尽可能使得数据都比较接近平均值。那么这题贪心策略应该是这样的：首先算出平均值$s/n$，把数据从小到大排序，如果某个人的钱低于该值，那么他一定是将钱全部支付，然后其余不够的其他人平摊。但是，由于之前那个人钱不够，那么就会导致剩下人支付的平均值会增大，所以在这个平摊过程中很有可能存在某个人钱又低于这个平均值，又需要剩下的人平摊。如此反复，直到支付完成。
C++代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int n, s, cnt;
int a[500010];
int main()
{
scanf("%d%d", &n, &s);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
sort(a, a + n);
double ave = s * 1.0 / n, cur_ave = ave, sum = 0;
for (int i = 0; i < n; i++)
{
if (a[i] <= cur_ave)
{
s -= a[i];
sum += (ave - a[i]) * (ave - a[i]);
cur_ave = s * 1.0 / (n - i - 1);// 当前平均值
}
else sum += (cur_ave - ave) * (cur_ave - ave);
}
printf("%.4lf", sqrt(sum / n));
return 0;
}
最新加入的第11组数据需要将double 改为 long double并修改输出才能通过
感谢！
感谢！看到差了0.0001差点心态崩了
心态崩了，将哪个改成long double
啥情况，加了 long double 答案全变成0了
输出那里也要改
long double 的输入输出格式为 ： %Lf
### 感谢
orz
没有证明
牛逼
根本过不了的，这里也错了 s -= a[i];
sum += (ave - a[i]) * (ave - a[i]);
cur_ave = s * 1.0 / (n - i - 1);// 当前平均值 。
想问一下用double数组存下来，答案会不对
为啥在 a[i] > cur_ave 的时候不更新s的值；
排序之后如果a[i] > cur的话后面都是大于cur的， cur不会再变了
老哥，else里面 不应该是 sum += (a[i] - cur_ave) * (a[i] - cur_ave)); // cur_ave不是当前平均值吗
cur_ave是动态的，是剩余下价格的平均值，而ave是总价的平均值。else当中是
a[i] > cur_ave，就是说i号人的钱大于剩余下价格的钱，显然它是能够支付cur_ave的。qwq，我理解这里面的意思， 我不太理解的是这里的 sum+= (a[i] - cur_ave) ^ 2 , 因为这里的 sum 不是 a[i]与平均值的差 在平方， if()里面是 a[i] 与 平均值的差的平方，那else中 a[i]还是a[i], 但是cur_ave是 当前平均值， 说我是不是别在哪里了
cur_ave是是付的价钱，if里面的a[i]也是付的钱
if里面是a[i]小于平均值s/n,a[i]全部放进去,else 是a[i]大于平均值,放一部分就行