AcWing 1235. 付账问题
原题链接
中等
作者:
彩
,
2024-01-22 15:20:06
,
所有人可见
,
阅读 43
没看y总之前,自己胡乱写的一种想法
简单来说就是:尽可能地去减小(bi - s/n)这一项
代码只是能过,并未优化(貌似也不慢 OVO)
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 500010;
int n;
long double s;
int a[N];
int main()
{
scanf("%d%llf", &n, &s);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
long double aver = s / n;
sort(a + 1, a + 1 + n);
long double res = 0;
long double ans = 0; //差值
int k;
for(int i = 1; i <= n; i++)
{
if(a[i] <= aver)
{
ans += aver - a[i];
res += (aver - a[i]) * (aver - a[i]);
}
else
{
k = i;
break;
}
}
long double cnt = ans / (n - k + 1);
int i = k, j = k;
while(i != n)
{
if(a[i] - aver < cnt)
{
res += (a[i] - aver) * (a[i] - aver);
ans -= (a[i] - aver);
cnt = ans / (n - i);
i++;
}
else
{
res += cnt * cnt;
ans -= cnt;
i++;
}
}
res += ans * ans;
res /= n;
printf("%.4Lf\n", sqrt(res));
return 0;
}