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

不就是找最小的k - 1个数，和最大的k - 1 个数吗？

leetcode 410

huorili 发表于 2019-11-22 21:55
有一个思路，仅供参考。
找最小最大值，好绕口，其实等价于让你把这个数组平均分，尽可能平均分。这样取出 ...

你这个想法也有点问题，比如一个特别大的数，应该单独放一个，但是如果前面sorted数组都evenly分布在了篮子里，那这个特别大的数就会跟其他数一起，让结果偏大。

这题二分法肯定不行，因为他不是按照原来的顺序找min max of k subarrays. 见刷题网410，Split Array Largest Sum. 这题可以binary search因为满足这个条件
既然这题要subsets.那目前我想到的只能记忆化DFS了。

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

四代目。。。我看你回复了很多人。。我算法不太好。。问你下哈
这个题 为啥不找最小的k个数  ，比如说K=2 ， 我sort下。。取前2个加起来 不就是答案的要求么？ 为啥一定要用记忆化dfs呢。。

这个问题对应于一个经典的调度问题：Scheduling on identical machines to minimize maximum completion time

两个基本结论：
--
1. 问题本身是NP-hard，即使对于k = 2的情况。
2. 存在总时间 O(n log(n)) 的近似分配策略，其给出的分配是 4/3-competitive 的，也就是说对于任意一组输入，假设最优解给出的最小值是 X 的话，那么近似算法给出的结果不会比 1.333 X 更差。

参考这个PPT：http://mat.uab.cat/~alseda/MasterOpt/orv2.pdf
在PPT里面搜包含关键字“ P||Cmax ”的部分

一剑终情 发表于 2019-11-23 06:14
留图不留种，菊。。
sorry 走错论坛了

留题不留号

isnt a leetcode question?

load balancing 问题啊， 复杂度应该是np-c？最优解sum应该只能暴力找，但是可以用greedy approximate一个最大不超过2*optimal sum的答案