本文由 简悦 SimpRead 转码， 原文地址 https://juejin.im/post/5af80310f265da0b8636585e
发出一个固定金额的红包，由若干个人来抢，需要满足哪些规则？
1. 所有人抢到金额之和等于红包金额，不能超过，也不能少于。
2. 每个人至少抢到一分钱。
3. 要保证所有人抢到金额的几率相等。
小灰的思路是什么样呢？
每次抢到的金额 = 随机区间 (0, 剩余金额)
为什么这么说呢？让我们看一个栗子：
假设有 10 个人，红包总额 100 元。
第一个人的随机范围是（0，100 元)，平均可以抢到 50 元。
假设第一个人随机到 50 元，那么剩余金额是 100-50 = 50 元。
第二个人的随机范围是 （0， 50 元），平均可以抢到 25 元。
假设第二个人随机到 25 元，那么剩余金额是 50-25 = 25 元。
第三个人的随机范围是 （0， 25 元），平均可以抢到 12.5 元。
以此类推，每一次随机范围越来越小。
方法 1：二倍均值法
剩余红包金额为 M，剩余人数为 N，那么有如下公式：
每次抢到的金额 = 随机区间 （0， M / N X 2）
这个公式，保证了每次随机金额的平均值是相等的，不会因为抢红包的先后顺序而造成不公平。
举个栗子：
假设有 10 个人，红包总额 100 元。
100/10X2 = 20, 所以第一个人的随机范围是（0，20 )，平均可以抢到 10 元。
假设第一个人随机到 10 元，那么剩余金额是 100-10 = 90 元。
90/9X2 = 20, 所以第二个人的随机范围同样是（0，20 )，平均可以抢到 10 元。
假设第二个人随机到 10 元，那么剩余金额是 90-10 = 80 元。
80/8X2 = 20, 所以第三个人的随机范围同样是（0，20 )，平均可以抢到 10 元。
以此类推，每一次随机范围的均值是相等的。
程序输出结果如下：
抢到金额：2.92
抢到金额：1.48
抢到金额：3.05
抢到金额：0.53
抢到金额：0.45
抢到金额：1.36
抢到金额：1.02
抢到金额：1.99
抢到金额：1.3
抢到金额：0.48
抢到金额：0.83
抢到金额：2.89
抢到金额：0.94
抢到金额：2.11
抢到金额：3.13
抢到金额：0.91
抢到金额：2.64
抢到金额：2.02
抢到金额：2.88
抢到金额：1.13
抢到金额：2.09
抢到金额：1.37
抢到金额：2.41
抢到金额：2.13
抢到金额：1.32
抢到金额：0.44
抢到金额：1.62
抢到金额：1.89
抢到金额：2.23
抢到金额：0.44
方法 2：线段切割法
何谓线段切割法？我们可以把红包总金额想象成一条很长的线段，而每个人抢到的金额，则是这条主线段所拆分出的若干子线段。
如何确定每一条子线段的长度呢？由 “切割点” 来决定。当 N 个人一起抢红包的时候，就需要确定 N-1 个切割点。
因此，当 N 个人一起抢总金额为 M 的红包时，我们需要做 N-1 次随机运算，以此确定 N-1 个切割点。随机的范围区间是（1， M）。
当所有切割点确定以后，子线段的长度也随之确定。这样每个人来抢红包的时候，只需要顺次领取与子线段长度等价的红包金额即可。
这就是线段切割法的思路。在这里需要注意以下两点：
1. 当随机切割点出现重复，如何处理。
2. 如何尽可能降低时间复杂度和空间复杂度。
—————END—————
喜欢本文的朋友们，欢迎长按下图关注订阅号程序员小灰，收看更多精彩内容
