付账问题
几个人一起出去吃饭是常有的事。
但在结帐的时候,常常会出现一些争执。
现在有 $n$ 个人出去吃饭,他们总共消费了 $S$ 元。
其中第 $i$ 个人带了 $a_{i}$ 元。
幸运的是,所有人带的钱的总数是足够付账的,但现在问题来了:每个人分别要出多少钱呢?
为了公平起见,我们希望在总付钱量恰好为 $S$ 的前提下,最后每个人付的钱的标准差最小。
这里我们约定,每个人支付的钱数可以是任意非负实数,即可以不是 $1$ 分钱的整数倍。
你需要输出最小的标准差是多少。
标准差的介绍:标准差是多个数与它们平均数差值的平方平均数,一般用于刻画这些数之间的“偏差有多大”。
形式化地说,设第 $i$ 个人付的钱为 $b_{i}$ 元,那么标准差为 :
输入格式
第一行包含两个整数 $n$、$S$;
第二行包含 $n$ 个非负整数 $a_{1}, …, a_{n}$。
输出格式
输出最小的标准差,四舍五入保留 $4$ 位小数。
数据范围
$1 \leq n \leq 5 \times 10^{5}$,
$0 \leq a_{i} \leq 10^{9}$,
$0 \leq S \leq 10^{15}$。
输入样例1:
5 2333 666 666 666 666 666
输出样例1:
0.0000
输入样例2:
10 30 2 1 4 7 4 8 3 6 4 7
输出样例2:
0.7928
解题思路
我们的目的是使得方差$$\sqrt{\frac{\left( {b_{1} - \frac{s}{n}} \right)^{2} + \left( {b_{2} - \frac{s}{n}} \right)^{2} + \cdots + \left( {b_{n} - \frac{s}{n}} \right)^{2}}{n}}$$最小化。
我们的贪心策略是每个人付的钱应该尽可能平均,这样方差才小:
- 如果每一个$a_{i} \geq \frac{s}{n}$,则每一个$b_{i}$都取$\frac{s}{n}$。
- 如果某一个$a_{i} < \frac{s}{n}$,则对应的$b_{i} = a_{i}$,有多少给多少,少给的钱$\frac{s}{n} - a_{i}$则分摊给其他钱数比他多的人。
下面证明一下这种做法是对的。
首先有不等式$$\sqrt{\frac{x_{1}^{2} + x_{2}^{2} + \cdots + x_{n}^{2}}{n}} \geq \frac{x_{1} + x_{2} + \cdots + x_{n}}{n}$$当$x_{1} = x_{2} = \cdots = x_{n}$时取等号,即取到最小值。
在$\sqrt{\frac{x_{1}^{2} + x_{2}^{2} + \cdots + x_{n}^{2}}{n}}$中的$x_{i}$对应于方差公式中的$b_{i} - \frac{s}{n}$。我们把每一个$b_{i} - \frac{s}{n}$都加起来,得到$${\sum\limits_{i = 1}^{n}{b_{i} - \frac{s}{n}}} = {\sum\limits_{i = 1}^{n}b_{i}} - n \cdot \frac{s}{n} = s - s = 0$$因此有$$\sqrt{\frac{\left( {b_{1} - \frac{s}{n}} \right)^{2} + \left( {b_{2} - \frac{s}{n}} \right)^{2} + \cdots + \left( {b_{n} - \frac{s}{n}} \right)^{2}}{n}} \geq 0$$且当$b_{1} - \frac{s}{n} = b_{2} - \frac{s}{n} = \cdots = b_{n} - \frac{s}{n}$,即$b_{1} = b_{2} = \cdots = b_{n}$取最小值0。证明了第一种情况,当每一个$a_{i} \geq \frac{s}{n}$,$b_{i} = \frac{s}{n}$。
然后对于第二种情况,如果某一个$a_{i} < \frac{s}{n}$,用反证法,对应的$b_{i}$取一个小于$a_{i}$的值${b'}_{i}$(${b'}_{i}$的值不可能大于$a_{i}$),${\left({b'}_{i} - \frac{s}{n} \right)}^{2} - {\left( b_{j} - \frac{s}{n} \right)}^{2}$会更小。我们可以找到一个$b_{j}$满足$b_{j} > \frac{s}{n}$,我们知道当${b'}_{i}$与$b_{j}$相差很小时,${\left({b'}_{i} - \frac{s}{n} \right)}^{2} - {\left( b_{j} - \frac{s}{n} \right)}^{2}$才会变小,而又因为${b'}_{i} < a_{i} < \frac{s}{n} < b_{j}$,这意味着我们可以把${b'}_{i}$继续取大到$a_{i}$,使得${b'}_{i}$与$b_{j}$的差变小,从而${\left({b'}_{i} - \frac{s}{n} \right)}^{2} - {\left( b_{j} - \frac{s}{n} \right)}^{2}$变得更小,矛盾。
具体的做法是,先将$a_{i}$排序,从前往后遍历,如果$a_{1} < \frac{s}{n}$,那么$b_{i}$必然取$a_{i}$,同时剩下的人还要尽可能分摊$a_{1}$没付的钱。对于公式$$\sqrt{\frac{\left( {b_{1} - \frac{s}{n}} \right)^{2} + \left( {b_{2} - \frac{s}{n}} \right)^{2} + \cdots + \left( {b_{n} - \frac{s}{n}} \right)^{2}}{n}}$$$b_{1}$已经固定了,能变化的只有后面的人,但后面的人要交的钱也是固定的,$b_{2} + \cdots + b_{n} = s - a_{i}$,通过均值不等式,我们发现从$i = 2$往后每一个$b_{i}$取$\frac{s - a_{i}}{n - 1}$,才能使得$\left( {b_{2} - \frac{s}{n}} \right)^{2} + \cdots + \left( {b_{n} - \frac{s}{n}} \right)^{2}$最小。剩下的分析同理,与贪心策略一样,如果发现某一个$a_{i}$大于当前要分的钱的平均数,那么就按照情况一来处理。
当时写了一个错误代码,思路是把$a_{i}$小于等于当前要分的钱的平均数的人找出来,然后这些人都各种交$a_{i}$,把剩余的钱都交给后面的人分,与上面的方法不同的是,我的方法是一段一段分的,效果肯定不如上面的一个一个人分的好。
#include <cstdio> #include <cmath> #include <algorithm> using namespace std; const int N = 5e5 + 10; const double eps = 1e-8; double a[N], b[N]; int find(int left, int right, double val) { while (left < right) { int mid = left + right >> 1; if (a[mid] - val > eps) right = mid; else left = mid + 1; } return left; } void dfs(int left, int right, double s) { double avg = s / (right - left + 1); int n = find(left, right, avg); if (n == left) { for (int i = left; i <= right; i++) { b[i] += avg; } return; } for (int i = left; i < n; i++) { b[i] += a[i]; s -= a[i]; } dfs(n, right, s); } int main() { int n; double s; scanf("%d %lf", &n, &s); for (int i = 0; i < n; i++) { scanf("%lf", a + i); } sort(a, a + n); dfs(0, n - 1, s); double ret = 0, avg = s / n; for (int i = 0; i < n; i++) { ret += (b[i] - avg) * (b[i] - avg); } ret = sqrt(ret / n); printf("%.4f", ret); return 0; }Wrong Answer Code
AC代码如下:
1 #include <cstdio> 2 #include <cmath> 3 #include <algorithm> 4 using namespace std; 5 6 const int N = 5e5 + 10; 7 const double eps = 1e-6; 8 9 int a[N]; 10 11 int main() { 12 int n; 13 double s; 14 scanf("%d %lf", &n, &s); 15 for (int i = 0; i < n; i++) { 16 scanf("%d", a + i); 17 } 18 19 sort(a, a + n); 20 21 long double ret = 0, avg = s / n; 22 for (int i = 0; i < n; i++) { 23 double t = s / (n - i); // 当前要分的钱的平均数 24 if (a[i] - t < eps) t = a[i]; // 如果当前的人的钱小于平均数,则他要交的钱是a[i],否则要交的钱就是平均数 25 ret += (t - avg) * (t - avg); 26 s -= t; 27 } 28 printf("%.4llf", sqrt(ret / n)); 29 30 return 0; 31 }
参考资料
AcWing 1235. 付账问题(蓝桥杯C++ AB组辅导课):https://www.acwing.com/video/734/