1235. 付账问题(均值不等式贪心)

https://www.acwing.com/problem/content/1237/

均值不等式贪心

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 5e5+10;
long double s;
long double sum;
int a[N];
double b[N];
int n;
long double res;
int main()
{
    cin >> n >> s;
    for(int i=0;i<n;i++)cin >> a[i];
    sort(a,a+n);
    long double avg=s/n;;
    for(int i=0;i<n;i++)
    {
        b[i]=s/(n-i);//此时的平均数
        if(a[i]<b[i])b[i]=a[i];//钱不够,有多少给多少
        res+=(b[i]-avg)*(b[i]-avg);
        s-=b[i]; //剩余需要付的钱
    }
    printf("%.4Lf\n",sqrt(res/n));
    return 0;
}