红包功能需要满足哪些具体规则呢？

  1. 所有人抢到的金额之和要等于红包金额，不能多也不能少。
  2. 每个人至少抢到1分钱。
  3. 要保证红包拆分的金额尽可能分布均衡，不要出现两极分化太严重的情况。

二倍均值法

假设剩余红包金额为m 元，剩余人数为n ，那么有如下公式。
随机分配方法 - 图1
这个公式，保证了每次随机金额的平均值是相等的，不会因为抢红包的先后顺序而造成不公平。
举个例子如下。
假设有5个人，红包总额100元。
100÷5×2=40，所以第1个人抢到的金额随机范围是[0.01，39.99] 元，在正常情况下，平均可以抢到20元 。
假设第1个人随机抢到了20元，那么剩余金额是80元。
80÷4×2=40，所以第2个人抢到的金额的随机范围同样是[0.01，39.99] 元，在正常的情况下，还是平均可以抢到20元 。
假设第2个人随机抢到了20元，那么剩余金额是60元。
60÷3×2=40，所以第3个人抢到的金额的随机范围同样是[0.01，39.99] 元，平均可以抢到20元 。
以此类推，每一次抢到金额随机范围的均值是相等的。 :::info 这样做真的是均等的吗？如果第1个人运气很好，随机抢到39元，第2个人所抢金额的随机区间不就缩减到[0.01 ，60.99] 元了吗？ ::: 这个问题提得很好。第1次随机的金额有一半概率超过20元，使得后面的随机金额上限不足39.99元；但相应地，第1次随机的金额同样也有一半的概率小于20元，使得后面的随机金额上限超过39.99元。因此从整体来看，第2次随机的平均范围仍然是[0.01 ，39.99] 元。

  1. public class DivideRedPackage {
  2.     public static List<Integer> divideRedPackage(Integer totalAmount, Integer totalPeopleNum) {
  3.         ArrayList<Integer> amountList = new ArrayList<>();
  4.         Integer restAmount = totalAmount;
  5.         Integer restPeopleNum = totalPeopleNum;
  6.         Random random = new Random();
  7.         for (int i = 0; i < totalPeopleNum - 1; i++) {
  8.             // 随机范围
  9.             int amount = random.nextInt(restAmount / restPeopleNum * 2 - 1) + 1;
  10.             restAmount -= amount;
  11.             restPeopleNum--;
  12.             amountList.add(amount);
  13.         }
  14.         amountList.add(restAmount);
  15.         return amountList;
  16.     }
  18.     public static void main(String[] args) {
  19.         List<Integer> amountList = divideRedPackage(1000, 10);
  20.         for (Integer amount : amountList) {
  21.             System.out.println(new BigDecimal(amount).divide(new BigDecimal(100)));
  22.         }
  23.     }

线段切割法

何谓线段切割法？我们可以把红包总金额想象成一条很长的线段，而每个人抢到的金额，则是这条主线段所拆分出的若干子线段。
image.png
如何确定每一条子线段的长度呢？
由“切割点”来决定。当n 个人一起抢红包时，就需要确定n -1个切割点。
因此，当n 个人一起抢总金额为m 的红包时，我们需要做n -1次随机运算，以此确定n-1个切割点。随机的范围区间是[1， m -1]。
当所有切割点确定以后，子线段的长度也随之确定。此时红包的拆分金额，就等同于每个子线段的长度。
这就是线段切割法 的思路，在这里需要注意以下两点。

  1. 当随机切割点出现重复时，如何处理。
  2. 如何尽可能降低时间复杂度和空间复杂度。