人员分组问题

[n0th1ng]

自己想到的一个问题

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

一般算法是怎样的？

[0ZXYDDu796nVCFxq]

10 个人分 3 组为什么不是 8,1,1 ？

[n0th1ng]

@gstqc 少写了个条件，尽量平均分给前面的组

[GuuJiang]

“尽量分到前面”缺乏准确的定义，(3,3,3,2)难道不是比(4,4,2,1)更“平均”？

[jmc891205]

找到比 m 小的最大的能被 n-1 整除的数字 k
然后答案就是 k/(n-1), k/(n-1), ..., k/(n-1), m-k

[n0th1ng]

@GuuJiang 那就再加一个条件，尽可能多的分给前面的组

[GuuJiang]

@n0th1ng
如果按“尽可能多的分给前面的组”，那么 11 就应该是(8,1,1,1)
如果是“平均的部分占比最多”，那么(3,3,3,2)应该是比(4,4,2,1)更优

你还是先把定义想清楚吧，或者如果你是想解决某个实际中的场景，不妨说下原始问题，以免成为一个 XY 问题

[mxT52CRuqR6o5]

你把 [尽量多的往前面组里分] 讲明白了不就自然能写出来了
你这属于猜产品经理想法题，而不是算法题

[zhuangjia]

尽量多的往前面组里分:
把 13 个人分到 4 个组里，可分成(4,3,3,3),但根据要求，要分成(4,4,4,1) ==> (5,5,2,1) 看起来更符合条件

[wolfie]

16 分 4 组，是 [5, 5, 5, 1] 还是 [5, 5, 4, 2]
这就没有标准答案，同样地参数，你扔给产品 2 次，都不一定有相同结果。

[n0th1ng]

@GuuJiang 你说的对，11 分 4 组的最优解是（ 3,3,3,2 ）

[n0th1ng]

谢谢各位，我再捋捋

[GuuJiang]

@n0th1ng
如果是这样的话就非常简单了，前面 n-1 组是 ceil(m/n)，剩下的放最后一组

PS：如果不想使用浮点运算及 ceil 函数，可以使用(m+n-1)/n 来代替