[数据结构与算法]付账问题_模拟_高精度

P1367 - [蓝桥杯2018初赛]付账问题 - New Online Judgehttp://oj.ecustacm.cn/problem.php?id=1367

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 4;
double S;
int n;
vector<double>ms;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> S;
    double avg = S / n; // 总平均数
    double sum = 0;
    int cnt = n;
    for (int i = 0; i < n; i++) {
        double a;
        cin >> a;
        if (a < avg || abs(avg - a) < 1e-4) {
            sum += (a - avg) * (a - avg);
            S -= a;
            cnt--;
        } else {
            ms.push_back(a);
        }
    }
    sort(ms.begin(), ms.end());
    for (int i = 0; i < ms.size(); i++) {
        if (ms[i] * (ms.size() - i) < S) {
            sum += (ms[i] - avg) * (ms[i] - avg);
            S -= ms[i];
            cnt--;
        } else {
            break;
        }
    }
    double t = S / cnt;
    sum += (t - avg) * (t - avg) * cnt;
    printf("%.4f", sqrt(sum / n));
    return 0;
}