付账问题

付账问题

几个人一起出去吃饭是常有的事。

但在结帐的时候,常常会出现一些争执。

现在有 $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}}$$最小化。

  我们的贪心策略是每个人付的钱应该尽可能平均,这样方差才小:

  1. 如果每一个$a_{i} \geq \frac{s}{n}$,则每一个$b_{i}$都取$\frac{s}{n}$。
  2. 如果某一个$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/

上一篇:读取一个字符串,字符串可能含有空格,将字符串逆转,原来的字符串与逆转后字符串相同,输出0,原字符串小于逆转后字符串输出 - 1, 大于逆转后字符串输出1。


下一篇:C语言拯救者 (分支和循环语句--3)