P8664 [蓝桥杯 2018 省 A] 付账问题 题解

· · 题解

思路

题意:计算在总付款量为 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;
}

完结撒花