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

phpfpm

149 天前

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

6HWcp545hm0RHi6G

149 天前

问了下 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%，这是题目设定导致的矛盾

Projection

149 天前

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

chachi

149 天前

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

cc666

149 天前

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

Wxh16144

149 天前

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

tenserG

149 天前

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

moudy

149 天前

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

a0000

149 天前

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

geelaw

149 天前

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

- 红包金额必须是整数，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) 的多项式时间内完成．

tenserG

149 天前

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

geelaw

149 天前

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

snailsir

149 天前

https://mp.weixin.qq.com/s/tooCMin-kR1J9r4orOR5LQ

oaix

149 天前

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

```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))
```

renmu

149 天前

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

hxy100

149 天前

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

oaix

149 天前

https://gist.github.com/alex-lx/06fabd0b9a92830201fb34332da3e630

yidinghe

149 天前

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

sweat89

148 天前

@hxy100 v2 不是用来讨论代码的哈😂

sillydaddy

148 天前

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