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

蠡口原题啊

tbu 发表于 2019-11-22 14:44
蠡口原题啊

留图不留种，菊。。
sorry 走错论坛了

说原题不给题号，。。。

10楼说的对，这题是二分查找的终极形式，二分答案
二分答案说白了就是O(lgn)的枚举答案，兼容了枚举的暴力（比较容易想）和二分的优雅（时间复杂度低，几乎是最优解）
是居家旅行的必备良药

沙场小兵 发表于 2019-11-23 04:26
sort之后二分查找，可能对最小max范围是0～total sum

主要是check函数的写法

下限说错了，下限是所有元素里的最小值
sort是保证下一个元素是最小的
如果加入最小的都超限，则剩余所有num都超限，进而不可能

这个题的核心就是：在一个区间内装入尽可能多的元素

沙场小兵 发表于 2019-11-23 04:26
sort之后二分查找，可能对最小max范围是0～total sum

主要是check函数的写法

感觉不太行， 因为是subset，也就是说，check函数不能从左到右扫描吧。不是特别懂这个函数，所以可能说错了。

huorili 发表于 2019-11-23 03:07
兄弟不太行，有反例， 13， 10， 7， 5 ， 2 ，2, 2,2,2  不好意思啊

请问层主怎么想到这个反例的呀

mammothlee 发表于 2019-11-23 07:45
感觉不太行， 因为是subset，也就是说，check函数不能从左到右扫描吧。不是特别懂这个函数，所以可能说错 ...

要先sort

看起来就是蠡口原题 斯幺灵 是hard 的 二分

huorili 发表于 2019-11-23 03:07
兄弟不太行，有反例， 13， 10， 7， 5 ， 2 ，2, 2,2,2  不好意思啊

想到了另一个反例：【7,5,5,4,3】分成2个se.

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

额，利口题要求连续，可以二分

这个题看起来只能dfs的样子