Acwing 1235. 付账问题

思路

这是贪心的题目，首先我们要知道标准差（方差的根）表示的是数据的波动程度，其值越大波
动越大。要使得标准差小，我们就要尽可能使得数据都比较接近平均值。那么这题贪心策略应
该是这样的：首先算出平均值s/n，把数据从小到大排序，如果某个人的钱低于该值，那么他一
定是将钱全部支付，然后其余不够的其他人平摊。但是，由于之前那个人钱不够，那么就会导致
剩下人支付的平均值会增大，所以在这个平摊过程中很有可能存在某个人钱又低于这个平均值，
又需要剩下的人平摊。如此反复，直到支付完成。

代码如下

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=5e5+10;
int a[N];
int n;
int main(void)
{
    double sum,z=0;cin>>n>>sum;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+1+n);double ag=sum/n,cot;for(int i=1;i<=n;i++){
    cot=sum/(n-i+1);if(a[i]<cot)cot=a[i];z+=(ag-cot)*(ag-cot);sum-=cot;}printf("%.4lf",sqrt(z/n));
}