面试遇到怪题，大家有什么思路吗

1 先分保底
2 每一块钱 roll ，超过 30%的重新 roll

问了下 AI

# 分红包算法思路

## 问题理解
我们需要将总奖金 `m` 分给 `n` 个人，满足以下条件：
1. 每个人分到的金额不超过总奖金的 30%（即 ≤ 0.3m ）
2. 每个人至少分到 1 元
3. 所有分配金额之和等于总奖金 `m`

## 算法思路

### 1. 输入验证
首先检查输入是否有效：
- 总奖金 `m` 必须 ≥ `n`（因为每人至少 1 元）
- 人数 `n` 必须 ≥ 1

### 2. 初始分配
给每个人分配 1 元（满足下限），剩余金额为 `m - n`

### 3. 分配剩余金额
采用随机分配方法，但要确保每次分配不超过个人上限：
- 个人上限为 `min(0.3m - 1, remaining_amount)`
- 使用随机算法（如"二倍均值法"）分配剩余金额

### 4. 具体步骤
1. 初始化每个人为 1 元
2. 计算剩余金额 `remaining = m - n`
3. 当 `remaining > 0`:
- 计算当前可分配的最大金额 `max_per_person = min(0.3m - 1, remaining)`
- 为每个人随机分配 0 到`max_per_person`之间的金额（或使用其他公平算法）
- 确保分配后不超过个人上限和剩余总额
4. 返回分配结果

## Python 实现示例

```python
import random

def distribute_red_packet(m, n):
if m < n:
raise ValueError("总奖金不能少于人数")
if n < 1:
raise ValueError("人数必须大于 0")

# 每人至少 1 元
result = [1.0 for _ in range(n)]
remaining = m - n
max_per_person = 0.3 * m - 1 # 个人上限

for i in range(n):
if remaining <= 0:
break

# 当前可分配的最大值
current_max = min(max_per_person, remaining)
# 随机分配金额（可以使用更复杂的算法）
amount = random.uniform(0, current_max)
# 保留两位小数
amount = round(amount, 2)
result[i] += amount
remaining -= amount

# 处理可能的剩余几分钱（由于四舍五入）
if remaining > 0:
result[0] += round(remaining, 2)

# 再次确保没有超过上限
for i in range(n):
if result[i] > 0.3 * m:
# 调整超出部分
excess = result[i] - 0.3 * m
result[i] = 0.3 * m
# 将超出部分分配给其他人
for j in range(n):
if j != i and result[j] + excess <= 0.3 * m:
result[j] += excess
excess = 0
break

return result
```

## 注意事项
1. 浮点数精度问题：实际实现中可能需要处理小数点后两位
2. 随机性：可以使用更复杂的随机算法使分配更均匀
3. 边界情况：当 `m` 刚好等于 `n` 时，每人只能得 1 元
4. 当 `0.3m < 1` 时（即 m < 3.33 ），实际上限会高于 30%，这是题目设定导致的矛盾

先留个保底，然后从 [0, m - n] 区间内随机 n - 1 次划分出 n 个区间，每个人取一个区间 + 保底

应该有超限重 roll 机制
每个人就 roll 一次就能正好符合我觉着不可能，因为有保底和上限。

@xierqii
请不要在回答技术问题时复制粘贴 AI 生成的内容

这里也有讨论 https://developer.aliyun.com/article/1657640

@chachi 我也是这么想的，如果不按照方法三，就只能重试直到满足条件了。如果设计奖池大概可以提前打表，但是这题还是怪怪的，毕竟开放题没有标准答案

直接生成 n-1 个 0-1 之间的随机数并排序，每个人拿两个相邻随机数差值 x 30%（ m-0.01*n)+0.01

先分 1 块钱
每个人在上 0 到 0.3m 减已分奖金之间取随机值，直到总奖金分完，如果没分完，再来多轮

问题意思不清楚，需要明确所要的分布，假设：

- 红包金额必须是整数，m 是自然数．
- 数据满足 m >= n 且 0.3m >= 1 （其他情况平凡）．
- 需要的分布是

X = { (a_1, ..., a_n) | a_i in Z, 1 <= a_i <= 0.3m, sum of a_i = m }

上的均匀分布．

又假设 m, n 不大（具体来说建模为关于 m, n 多项式时间可接受），那么最朴素的思路就是……

固定 m, n 后，令

f(I, J) = |{ (a_1, ..., a_I) | a_i in Z, 1 <= a_i <= 0.3m, sum of a_i = J }|,

则 f(0, 0) = 1 且 f(0, J) = 0 对所有 J != 0 且

f(I, J) = sum of f(I - 1, J - a_I) over 1 <= a_I <= floor(0.3m).

考虑抽样算法 D(I, J) 表示“I 个人分配 J 元奖金”，则 D(I, J) 是：

- 以 f(I - 1, J - x) / f(I, J) 的概率抽取 x ，其中 1 <= x <= 0.3m 且 x in Z ．
- 把 x 作为 a_I 输出．
- 运行 D(I - 1, J - x)．

所要求的就是运行一次 D(n, m)．



补充细节留给楼主：证明上述 D(n, m) 可以在 (m+n) 的多项式时间内完成．

@Wxh16144 微信红包就是二倍均值法，估计标准答案就是二倍均值法跟线割法了。

@geelaw #10 一个简单的优化：D(I, J) 均匀随机出来一个 1 到 f(I, J) 的整数，然后按照 f 做“进位制展开”即可得到一个样本，无需递归/重新采样子问题。

不考虑分布的话，感觉可以这样分：

```python
import random


def sample(m, n):
low = 1
upper = m * 0.3

remain = m
result = []
for _ in range(n-1):
x = low + min(remain-low, upper) * random.random()
remain -= x
result.append(x)
result.append(remain)
random.shuffle(result)
return result


for i in range(10):
print(sample(100, 10))
```

如果最后一个人不符合条件，那就重新 roll

你们 v 站贴 Python 代码，缩进全无，简直要人命。

难道不是事先将红包先分好吗？先拆出 n 个红包，这个过程中可以二次调整，随后在领取时随机发。比如你的思路 2 中，发现有超过上限的就将超出部分补给最低的那个就行了。

v 站之前讨论过这个问题，这个问题可以看作是在一个多边形内随机取点。
“如何把一个数字 x 随机分成 y 个数字，这些数字≥a 且≤b”
/t/745915

红包金额从 1 到 x=0.3m ，基于红包 ID 做种子生成 1 到 x 的固定随机数序列共 n 个，每个人按自己随机数占总和的比领钱

如果没有要求 随机的话，很简单？
上限下限先分好，然后再随机。

1 ， 先每人派发下限, n *1

2 ， 令 (m - n ) = x (0.3m -1) +k, 其中 的商数 x 和余数 k
那么有 x 份上限，以及 剩余金额 k 供剩下的人抽取。

3 ，结果输出：x 份上限，剩下的 n-x 人从 k 里面随机抽取 再加 下限 1 。

补充：追加一个更像随机的 处理：
4 ，x 份上限 可以再和 n-x 中的 x 份 随机配对，然后把他们的金额混合后再随机分配一下。

不能每人一块钱，剩下的给老板吗 ？

为什么要领红包得时候，才生成一个随机的金额？
发红包的时候，就按照设计的随机算法，把每个的金额已经生成好了，然后再把超出 30%的匀一下

随机分红包说明奖金不高，直接买点吃的大家一起吃掉。

先每个人保底分配 1 元, 然后求出剩余奖金的平均值, 然后循环给每个用户随机分配奖金

循环随机分配时随机数动态分配, 每个用户随机范围为 0 到 剩余平均值 + 上次循环剩余奖金, 如果剩余平均值 + 上次循环剩余奖金 > %30-1, 则最小值 + (剩余平均值 + 上次循环剩余奖金 - %30-1).

大概思路如此, 理论上可以保证每次随机都会在上限内分配, 如果上一个人分配的少了, 下一个人就有更高概率分配更多一点.

//m 是金额，n 是人数
(function(m,n){
let result=[]
const maxValue = m * 0.3
const _n = Array.from({length:n}).map((_, i) => {
return {
index: i,
value: 1,
}
})

m = m - n


while(m){
const index = getRandomInt(_n.length)

_n[index].value++

if(_n[index].value > maxValue){
const removed = _n.splice(index, 1)
result.push(removed)
}
m--
}


result = [...result, ..._n].sort((a,b)=>a.index > b.index)

return result
}(1000,10))


function getRandomInt(max) {
return Math.floor(Math.random() * max);
}
一块钱一块钱分，您看这样行么。自己写的，还没优化过存储

随机+拒绝采样就是最简单也最实用的做法，不用想那么多复杂的……

@phpfpm 这中方式感觉存在最坏情况，永远分不完

方法二：第 i 个人并不是 range （ 0 ，0.3*m-1 ），而是 range （ max(0, m-0.3*(n-i)) ，0.3*m-1 ）也就是要保证 i 至少分一个钱数，让后面人卡着最大值能满足不超。当然这样会导致后几个人得到大红包的概率高，只需排好再打乱排序即可

你的思路二扩展下就行
思路二 下限当作保底，先每个人分 1 元保底，剩下奖金池是 m-n ，1 到 n-1 人领取随机生成 range （ 0 ，0.3*m-1 ）的红包，最后一个人拿到剩余，这样保证了下限，但是上限还是会超，如果前面 n-1 个人没分完总奖金的（ 1-30%）=70%，剩下一个人就会超过上限 30%

[当最后一人超出 30%,则取 30%，多出的金额给剩下的没有达到上限的人随机] 重复操作这个步骤就行

想到一种思路
写个 judge 函数，判断方案（顺序领红包金额的数组）是否满足要求
然后死循环 random 出红包队列数组，直到有个数组满足 judge

1 + ramdom(0, min(0.3m, 剩余奖金))
先分一元，每个人红包最大值就是剩余奖金与总奖金 30%取小值，0~红包最大值取随机数，再加上先分的 1 元

@zoyao 抱歉，想简单了，这样子好像会超上限

大脑：这不是简简单单有手就行
手：报错、报错、报错、奖金没分完、奖金分超了、概率不平均

额滴神啊

// php 代码，带 <? 提示 cf 拦截
$fee = 100; // 总奖金 可以是 100k
$count = 4; // 不超过 30% 至少要 4 个人及以上

$list = [];
$remain = $fee;

for ($i = 0; $i < $count; $i++) {
$left = $count - $i;
$max = min($remain, $fee * 0.3);
$min = max(1, $remain - ($left - 1) * $max);
$amount = ($i === $count - 1) ? $remain : mt_rand(ceil($min), $max);
$list[] = $amount;
$remain -= $amount;
}

// 最后 10w 测试发现，第一个抽的人很亏，所以把所有人的抽奖打乱一下
//第 0 人 => 2049658
//第 1 人 => 2524927
//第 2 人 => 2763712
//第 3 人 => 2761703

shuffle($list);

// 当当当当 10w 结果看上去 OK 了
//第 0 人 => 2525703
//第 1 人 => 2524015
//第 2 人 => 2523623
//第 3 人 => 2526659

这不就是 softmax 吗。都不用 e ，直接在 0 到 max 之间 random N 个数，然后每个数除以总和乘以红包总额，向下取整，把最后的差额一人一块分了。

思路就是默认每人一块,剩下的钱一块块的随机给一个人
import random

def main(m, n):
if m > n >0:
m_30 = m * 0.3
print("单人上限:", m_30)
if n-1+int(m*0.3) > m or m/n > m_30: # 判定平均分是否会超过 30%等乱七八糟的可能
return []

re_ = [1 for i in range(n)] # 默认每人一块
re_n = [i for i in range(n)] # 分钱团队
m -= n # 去掉默认的钱
while m > 0: # 奖池还有钱
random_n = random.choice(re_n) # 随机没有超过限额的人
re_[random_n] += 1 # 这个人多一块
if re_[random_n] > m_30: # 这个人超过了限额
re_[random_n] -= 1 # 这个人少一块
re_n.pop(re_n.index(random_n)) # 分钱团队删除这个人
continue # 继续分钱
m -= 1 # 奖池减少一块
return re_
elif m == n:
return [1 for i in range(n)]
else:
return []

if __name__ == "__main__":
s = 500 # 总奖金
r = 17 # 总人数
result = main(s, r)
if result:
print(result)
else:
print("No solution")

@Yanlongli 修改
$max = min($remain, $fee * 0.3) - ($left - 1);

我感觉本质上是一个约束比较宽泛的约束满足问题。与地图填色、八皇后之类的是一类问题。
N 个变量，x_1, x_2,...x_n
有整体约束：x_1+x_2+....x_n=M
变量约束：1<x_i<M/N

然后各类搜索算法跑起来～

在创建红包的时候就按数量分好金额池，然后随机抽就完了

@xierqii 回答技术问题不能用 AI 你是一点都不看 @livid

@viking602 谢谢。那个账号已经被彻底 ban 。

思路三没什么问题，你可能纠结的"随机"是数学上的随机，工程上只要在最后分的时候把顺序打乱，整体就是公平的。类似于切蛋糕的和分蛋糕的不是同一个人，无论切蛋糕的人怎么切，只要分蛋糕的人闭着眼睛随机分，大家的期望就都一样

哎……多少次了，AI 回答贴个分享链接就行了不要贴结果不要贴结果，又拜拜了一个账号

上下限差太多，又限制单包。。基本下限就没用了。

@phpfpm @Exxfire 超过 30%不用重新 roll ，直接分给下一个不到 30%的

如果是 2 个人分 100 块钱, 会怎么样?

1 楼的答案很好啊. 补充一下:
1. 可以先做判断, 对不能满足情况的输入进行报错.
2. 再看 47 楼的回答, 也就是 roll 的时候, 把已经达到上限的元素剔除就好了

想了一下，感觉只能事先按人数分配好红包金额，不能每次去获取的时候再去计算红包金额。在此前提下，想了一个方案：
首先给每个人分配下限 1
然后循环 每次随机取 1 人 然后再在 0.3m-已分配给这个人的金额 中随机一个金额
判断这个随机金额+已分配金额是否达到 m ，没达到就给这个人分配这个随机的金额，继续循环
如果这个随机金额+已分配金额超过了 m ，那随机金额就取 m-已分配金额，结束循环

用 js 写了一下 金额是乘了 100 用整数算
```
function calc(m, n) {
const min = 100;
const max = 0.3 * m;
const res = new Array(n).fill(min);
let sum = res.reduce((a, b) => a + b, 0);

while (sum < m) {
const i = Math.floor(Math.random() * n);
let rand = Math.floor(Math.random() * (max - res[i]));
if (sum + rand > m) {
rand = m - sum;
}
res[i] += rand;
sum = res.reduce((a, b) => a + b, 0);
}
console.log(sum, res);
}
```

每个人依次生成随机数，如果满足条件且小于剩余钱数，给这个人分钱，对下一个人；
如果到了最后一个人那么判断剩余钱数是否满足条件。如果 OK 那么找到一个方案。否则前一个人重新来


import java.util.Arrays;
import java.util.Random;

public class RedBag {

private Random random = new Random();

public static void main(String[] args) {
int[] r = new RedBag().resolve(new int[10], 10,0, 100, 100);
System.out.println(Arrays.toString(r));
r = new RedBag().resolve(new int[10], 10, 0, 10, 10);
System.out.println(Arrays.toString(r));
}

/// result: Result for each persion
/// N: Total number of person
/// n: Current person, [0, N - 1]
/// M: Total money
/// m: How much money left
private int[] resolve(int[] result, int N, int n, int M, int m) {

// Last person, and the left money is OK
if (n == N - 1) {
if (m >= 1 && m < 0.3 * M) {
result[n] = m;
return result;
} else {
return null;
}
}

// left money cannot give at least $1 per person
if (m < N - n) {
return null;
}

int value = 0;
while (true) {
// Try to give some money to current person
int range = Math.min(m, (int) Math.floor(0.3 * M));
value = random.nextInt(range) + 1;
if (value < m) {
result[n] = value;
int[] r = resolve(result, N, n + 1, M, m - value);
if (r != null) {
return r;
}
}
}
}
}

这样的吗？

对于总量 m 和个数 n ，以及最大比例 r, 每次确定随机范围[x, y]

x >= 1
m - x <= (n - 1) * r * m 也即 x >= m - (n - 1) * r * m

-> x = max(1, m - (n - 1) * r * m)

y <= r * m
m - y >= (n - 1) * 1 也即 y <= m - (n - 1) * 1

-> y = min(r * m, m - (n - 1) * 1)

@rainbowhu r * m 直接换成固定值 最早的 m * 0.3 吧