付账问题（贪心问题、均值不等式）
几个人一起出去吃饭是常有的事。
但在结帐的时候，常常会出现一些争执。
现在有 n 个人出去吃饭，他们总共消费了 S 元。
其中第 i 个人带了 ai 元。
幸运的是，所有人带的钱的总数是足够付账的，但现在问题来了：每个人分别要出多少钱呢？
为了公平起见，我们希望在总付钱量恰好为 S 的前提下，最后每个人付的钱的标准差最小。
这里我们约定，每个人支付的钱数可以是任意非负实数，即可以不是 1 分钱的整数倍。
你需要输出最小的标准差是多少。
标准差的介绍：标准差是多个数与它们平均数差值的平方平均数，一般用于刻画这些数之间的“偏差有多大”。
形式化地说，设第 i 个人付的钱为 bi 元，那么标准差为 :
输入格式
第一行包含两个整数 n、S；
第二行包含 n 个非负整数 a1, …, an。
输出格式
输出最小的标准差，四舍五入保留 4 位小数。
数据范围
1≤n≤5×10^5,
0≤ai,S≤10^9
输入样例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
题解分析：
数学知识：均值不等式中平方平均数大于等于算术平均数
$\frac{X_1^2+X_2^2+…+X_n^2}{n}>=(\frac{X_1+X_2+…+X_n}{n})^2$
当且仅当x1=x2=…=xn时，取到最小值。
题目中需要求标准差最小值，标准查=方差开根号，方差满足前面那个平方平均数的式子，
这里假设所有人都带够了钱，因此b1+b2+…+bn=S，$b_1-\frac{S}{n}+b_2-\frac{S}{n}+…+b_n-\frac{S}{n}=0$，各项和为0，因此带入均值不等式可以得出
$\frac{(b_1-\frac{S}{n})^2+(b_2-\frac{S}{n})^2+…+(b_n-\frac{S}{n})^2}{n}>=0$，当且仅当
$b_1-\frac{S}{n}=b_2-\frac{S}{n}=…=b_n-\frac{S}{n}$时成立，带入b1+b2+…+bn=S得出每项等于$\frac{S}{n}$，这是最优解
那么如果n个人带的钱都大于 S/n 的平均数的话，都出 S/n 标准差就可以取到 0，
但是有可能有一部分人没有带够 S/n 元，那么他们应该把自己有的所有钱都出出来，尽可能靠近平均值 S/n ，
现在假设数组a为每个人带的钱数，数组b为每个人出的钱数， a1 < S/n， 那么 b1 = a1
然后对于$\frac{(b_1-\frac{S}{n})^2+(b_2-\frac{S}{n})^2+…+(b_n-\frac{S}{n})^2}{n}=\frac{(b_1-\frac{S}{n})^2}{n}+\frac{(b_2-\frac{S}{n})^2+…+(b_n-\frac{S}{n})^2}{n}$
因为等式右边的b1=a1，所以$\frac{(b_1-\frac{S}{n})^2}{n}$这部分已经是定值了，因此对于后面的人来说
$\frac{(b_2-\frac{S}{n})^2+…+(b_n-\frac{S}{n})^2}{n}$这个等式当 b2=b3=…=bn= (S-a1)/n 时，是最优的，后面的情况类似。
需要注意的是因为后面的人需要帮前面的人补足缺失的钱数，所以我们整个数组a必须从小到大排序
AC代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const double eps = 1e-6;
const int N = 5e5+5;
int a[N];
double b[N];
int main()
{
int n;
double s;
scanf("%d%lf", &n,&s);
for(int i=0; i<n; ++i){
scanf("%d", &a[i]);
}
sort(a,a+n);
double avg = s*1.0/n;
double ans = 0;
for(int i=0; i<n; ++i){
double cur = s*1.0/(n-i);
if(a[i]<cur) cur = a[i];
ans += (cur-avg)*(cur-avg);
s -= cur;
}
printf("%.4lf\n",sqrt(ans*1.0/n));
return 0;
}
