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

619899442 发表于 2019-11-22 19:38
想到了另一个反例：【7,5,5,4,3】分成2个se.

step 1 取2个最大： 7 / 5
step 2 取下一个加到sum最小的组:   7 / 5 5
step 3 取下一个加到sum最小的组:   7 4 / 5 5
step 4 取下一个加到sum最小的组:   7 4 / 5 5 3

answer 11

怎么加到sum最小的组，冒个泡就可以了

如果只需要最后的那个最小值，那一个min heap就行了。

1. 先从大到小排序
2. 把前K个最大的插入heap
3. 剩下的重复  pop heap， 加上下一个最大的， push to heap
最后返回堆顶

[1,2,3] and k=2 就是
step 2: heap 里面 2，3
step 3: 读出2， 放回去 2+1=3
返回3


【10,6,5,4,3,1】 k = 3
step 2: heap 里面 10，6， 5
step 3: 读出5， 放回去 5+4=9， heap 10 9 6
step 4: 读出6， 放回去 6+3=9， heap 10 9 9
step 5: 读出9， 放回去 9+1=10， heap 10 10 9
返回9


如果要求输出分类方法，那就需要一些额外的存储空间了

沙场小兵 发表于 2019-11-23 09:09
要先sort

Sort感觉也不大行，受楼上几位启发，想到一个反例：10，6，5，5，4 分成2组，最佳应该是 【10， 5】和【6，5，4】吧。。。 如果反例不对希望能指正。。 可能只能用dfs？

这题的特例 k=2 时，是经典的【划分问题】的变种。。。
【划分问题】即给定 n 个非负整数 a1, ..., an，问是否能找到若干个数组成集合 A，剩下的数组成集合 B，使得 sum(A) == sum(B)，其中 sum() 函数表示对集合中的元素求和。
【划分问题】本身就是 NP-Complete 了，这题当然只能靠 dfs 搜索了。。。

补充内容 (2019-11-23 01:44):
有很多人把P=NP证出来了呀，算法课教的东西都还给老师了吗。。。

补充内容 (2019-11-23 22:29):
用一个反例：array=[2,2,3,3]，k=2 基本就可以把那些二分答案都干掉了。。。

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

主要是check函数的写法
从左到右扫描ar...

此答案正确。今天太晚，明天我贴个code上来。

补充内容 (2019-11-23 01:21):
下限应该是数组中最大的元素，上线是所有数字之和

https://leetcode.com/problems/divide-chocolate/

337845818 发表于 2019-11-23 21:26
https://leetcode.com/problems/divide-chocolate/

楼主的这题不要求连续

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

主要是check函数的写法

反例：array=[2,2,3,3]，k=2

第一个是正解，可以再加一些判断，防止极限条件，比如有一个极大值，其它的都是1。二分的范范围应该是最大值到总和。

波风水门 发表于 2019-11-23 22:25
反例：array=[2,2,3,3]，k=2

你答案多少报一下

[2] [2,3,3] = 8
[3] [2,2,3] = 7
[2,2] [3,3] = 6
[2,3] [2,3] = 5