最近面了Oracle，有一题始终想不明白，希望各位大佬帮忙分析一下

Zetecx 发表于 2019-11-23 09:28
看起来就是蠡口原题 斯幺灵 是hard 的 二分

题干不一样，蠡口上面的题的partition是连续的，这个不是。。这个题应该没法在多项式复杂度内做完。。

波风水门 发表于 2019-11-23 16:45
这题的特例 k=2 时，是经典的【划分问题】的变种。。。
【划分问题】即给定 n 个非负整数 a1, ..., an，问 ...

我觉得你说的有道理，这个是经典的 load balancing问题， 应该是np c? 但是我记得可以用greedy 找到appoximate 最优解。排序加greedy 的 approximate 解最大等于两倍最优解