每日一题洛谷P8664 [蓝桥杯 2018 省 A] 付账问题c++

P8664 [蓝桥杯 2018 省 A] 付账问题 - 洛谷 (luogu.com.cn)

思路：要使方差小，那么钱不能一下付的太多，可以让钱少的全付玩，剩下还需要的钱再让钱多的付（把钱少的补上）。

将钱排序，遍历一遍，同时将小于平均数的钱加起来计算（平均数是动态，因为后面的钱总比前面的多，总能给前面补钱，这里的误区是直接把平均数设置为总钱数/人数，这样的结果比答案上的方差大），大于等于平均数的钱直接乘上剩下的人数进行计算并跳出循环。

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
#define int long long
signed main() {int n, s;cin >> n >> s;vector<int> a(n);for (int i = 0; i < n; i++)cin >> a[i];sort(a.begin(), a.end());double x = (double)s / (double)n;double c = 0;for (int i = 0; i < n; i++) {double left = (double)s / (double)(n - i);if ((double)a[i] < left) {c += (x - (double)a[i]) * (x - (double)a[i]);s -= a[i];}else {c += (x - left) * (x - left) * (n - i);break;}}c = sqrt(c / n);printf("%.4lf", c);return 0;
}