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

[tenserG]

分红包，上限是总奖金 30%，下线 1 元，输入奖金总数 m 和人数 n ，输出一个列表表示每个人红包

思路一 传统分红包办法，1 到 n-1 人领随机生成 range （ 1 ，0.3*m ）的红包，最后一个人拿到剩余，但是这样最后一个人可能会超出上下限

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

到这里基本时间就到了，感觉凉凉，复盘时候感觉无论怎么随机分，都没法保证刚好分完

思路三是搜索到的一种解法，先计算平均值 avg ，每个人两两一对，领取 avg+-random 的红包，如果人数是单数，则返回平均值。这样能保证分完，不过额真的随机么。

[lzxz1234]

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

[abc634]

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

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

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

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

[abc634]

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

[kapaseker]

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

[pierswu]

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

[E2gCaBAT5I87sw1M]

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

[InDom]

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

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

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

[runlongyao2]

//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);
}
一块钱一块钱分，您看这样行么。自己写的，还没优化过存储

[InkStone]

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

[Exxfire]

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

[chairuosen]

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

[edward1987]

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

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

[gxt92]

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

[zoyao]

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

[zoyao]

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

[Yanlongli]

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

额滴神啊

// 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

[littleW2B]

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

[knight618]

思路就是默认每人一块,剩下的钱一块块的随机给一个人
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]

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

[senghoo]

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

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