自动搬运

查看原文

来自洛谷，原作者为

	zhjx2023 **

搬运于2025-08-24 22:41:13，当前版本为作者最后更新于2024-01-23 16:46:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

题意:计算在总付款量为 $S$ 的前提下，使每个人付的钱的标准差最小。标准差的计算涉及到每个人支付的金额，需要找到一种支付方案，使得标准差最小。 显然这是一道贪心题，那么思路就来了:

1. 读取输入的总人数 $n$ 和总消费金额 $S$。
2. 读取每个人带的钱数 $a[i]$。
3. 将带的钱数升序排序。
4. 遍历每个人，计算其实际支付的金额 $ans$，取最小值为当前人应该支付的金额，更新总消费额 $s$，并计算偏差的平方。 ans = min(a[i], s / (n - i + 1)), s -= ans, cnt += (ans - sum) * (ans - sum);
5. 输出最终计算得到的标准差，四舍五入保留4位小数。

代码

#include <bits/stdc++.h>
#define ll long long
//#define cin std:cin
//#define cout std:cout
using namespace std;
const ll N = 1e7 + 10, MOD = 1e9 + 7;
ll n;
long double a[N], s, ans, cnt;
int main() {
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> s;
	long double sum = (s / n * 1.0);
	for (ll i = 1; i <= n; i++)	cin >> a[i];
	sort(a + 1, a + 1 + n);
	for (ll i = 1; i <= n; i++)
		ans = min(a[i], s / (n - i + 1)),
		s -= ans, cnt += (ans - sum) * (ans - sum);
	printf("%.4Lf", sqrt(cnt / n));
	return 0;
}

完结撒花