蓝桥杯|[蓝桥杯] 付账问题蓝桥杯|贪心

付账问题题目
几个人一起出去吃饭是常有的事。
但在结帐的时候，常常会出现一些争执。
现在有 n 个人出去吃饭，他们总共消费了 S 元。
其中第 i 个人带了 ai 元。
幸运的是，所有人带的钱的总数是足够付账的，但现在问题来了：每个人分别要出多少钱呢？
为了公平起见，我们希望在总付钱量恰好为 S 的前提下，最后每个人付的钱的标准差最小。
这里我们约定，每个人支付的钱数可以是任意非负实数，即可以不是 1 分钱的整数倍。
【蓝桥杯|[蓝桥杯] 付账问题】你需要输出最小的标准差是多少。
标准差的介绍：标准差是多个数与它们平均数差值的平方平均数，一般用于刻画这些数之间的“偏差有多大”。
形式化地说，设第 i 个人付的钱为 bi 元，那么标准差为 :

文章图片

输入格式
第一行包含两个整数 n、S；
第二行包含 n 个非负整数 a1,?…,?an。
输出格式
输出最小的标准差，四舍五入保留 4 位小数。
数据范围
1 ≤ n ≤ 5 × 105 0 ≤ a i , S ≤ 109 1≤n≤5×105 \\ 0≤ai,S≤109 1≤n≤5×1050≤ai,S≤109
输入样例

10 30
2 1 4 7 4 8 3 6 4 7

输出样例

0.7928

题解思路

首先算出平均值 s/n，把数据从小到大排序
如果某个人的钱低于该值，那么他将钱全部支付，然后其余不够的其他人平摊

#include #include #include using namespace std; const int N = 5 * 1e5 + 20; int n; double a[N], b[N], S; int main () { cin >> n >> S; for (int i = 0; i < n; i ++) cin >> a[i]; sort(a, a + n); double avg = (double)S / n; int start = 0; while (S > 0) { for (int i = start; i < n; i ++) { if (a[i] <= avg) { b[i] += a[i], S -= a[i], a[i] = 0; start = i + 1; } else { b[i] += avg, S -= avg, a[i] -= avg; } } avg = S / (n - start); }double sum = 0; for (int i = 0; i < n; i ++) sum += b[i]; avg = sum / n, sum = 0; for (int i = 0; i < n; i ++) sum += (b[i] - avg) * (b[i] - avg); printf("%.4lf", sqrt(sum / n)); return 0; }

题解二

来源：AcWing 1235. 付账问题

#include #include #include #include #include using namespace std; const int N = 500010; int n; int a[N]; int main() { double s; scanf("%d%lf", &n, &s); for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]); sort(a, a + n); double res = 0, avg = s / n; for (int i = 0; i < n; i ++ ) { double cur = s / (n - i); if (a[i] < cur) cur = a[i]; res += (cur - avg) * (cur - avg); s -= cur; }printf("%.4lf\n", sqrt(res / n)); return 0; }