自己想到的一个问题
把 m 个人分到有顺序的 n 个组 g1,g2,g3...gn 里,要求
例如
一般算法是怎样的?
1
0ZXYDDu796nVCFxq 2021-12-13 17:44:56 +08:00 via Android
10 个人分 3 组为什么不是 8,1,1 ?
|
3
GuuJiang 2021-12-13 18:06:38 +08:00 via iPhone
“尽量分到前面”缺乏准确的定义,(3,3,3,2)难道不是比(4,4,2,1)更“平均”?
|
4
jmc891205 2021-12-13 18:11:47 +08:00
找到比 m 小的最大的能被 n-1 整除的数字 k
然后答案就是 k/(n-1), k/(n-1), ..., k/(n-1), m-k |
6
GuuJiang 2021-12-13 18:28:54 +08:00
@n0th1ng
如果按“尽可能多的分给前面的组”,那么 11 就应该是(8,1,1,1) 如果是“平均的部分占比最多”,那么(3,3,3,2)应该是比(4,4,2,1)更优 你还是先把定义想清楚吧,或者如果你是想解决某个实际中的场景,不妨说下原始问题,以免成为一个 XY 问题 |
7
mxT52CRuqR6o5 2021-12-13 18:30:22 +08:00
你把 [尽量多的往前面组里分] 讲明白了不就自然能写出来了
你这属于猜产品经理想法题,而不是算法题 |
8
zhuangjia 2021-12-13 18:35:01 +08:00
尽量多的往前面组里分:
把 13 个人分到 4 个组里,可分成(4,3,3,3),但根据要求,要分成(4,4,4,1) ==> (5,5,2,1) 看起来更符合条件 |
9
wolfie 2021-12-13 18:35:36 +08:00
16 分 4 组,是 [5, 5, 5, 1] 还是 [5, 5, 4, 2]
这就没有标准答案,同样地参数,你扔给产品 2 次,都不一定有相同结果。 |
11
n0th1ng OP 谢谢各位,我再捋捋
|