这是一个创建于 1067 天前的主题，其中的信息可能已经有所发展或是发生改变。
自己想到的一个问题
把 m 个人分到有顺序的 n 个组 g1,g2,g3...gn 里，要求
- 每个组至少有 1 人
- 尽量往前面组里分
例如
- 把 10 个人分到 3 个组里，可分成(4,3,3),但根据要求，要分成(4,4,2)
- 把 13 个人分到 4 个组里，可分成(4,3,3,3),但根据要求，要分成(4,4,4,1)
- 把 11 个人分到 4 个组里，可分成(3,3,3,2),但根据要求，要分成(4,4,2,1)
一般算法是怎样的？
第 1 条附言 · 2021-12-13 18:03:30 +08:00
是尽量平均分到前面的组里
第 2 条附言 · 2021-12-13 18:25:29 +08:00
要求
每个组至少有 1 人
尽量平均分
尽量多的往前面组里分
每个组至少有 1 人
尽量平均分
尽量多的往前面组里分
 |
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 谢谢各位，我再捋捋
|
1
Select Language