琼瑶奶奶的爱情还是不成熟 - 未名空间MITBBS历史存档

琼瑶奶奶的爱情还是不成熟# Love - 情爱幽幽

E*a2017-05-07 07:05

1 楼

一个数组，N个正整数，分成x段，找一种分段法，minimize the maximum sum of x
pieces,
i.e.,
minimize: MAX OF {sum of piece_1, sum of piece_2, ..., sum of piece_X}
大家觉得这个题目如果用了很多提示，最后能做出来，是不是还不错了？

a*42017-05-07 07:05

2 楼

从小就能吃，很胖了，不让他吃他会大哭大闹。

a*n2017-05-07 07:05

3 楼

琼瑶奶奶总是不甘寂寞，时不常要闹些故事出来，刷下知名度。这些日子，为了失智老
公，和老公的孩子打嘴仗，吸引了众多眼球。琼瑶自打出道以来，一直争议不断，近些
年来，批评的声音愈发响亮，众人不满的主要是她的小说里的爱情故事过于理想化，对
年轻人毒害严重。我看她的问题是她对爱情的理解层次不太够，基本局限在激情阶段，
没有升华，不太成熟，有些幼稚，图样图森破，所以粉丝基本盘都是些未经世事的小女
孩子，老帮子很少。
成熟的大人们都知道，爱情固然重要，但她只是人和人众多关系里的一种，一部分；激
情在爱情中当然非常重要，但必须要经风雨、见世面，必须成长、升华才有意义，才真
正能够长久。以前看到一个女孩结婚前给她未来丈夫写的协议，里面有重要的一条就是
要求男的将来激情退却时仍有亲情，当时觉得这个女孩虽然小小年纪，但非常清醒、理
智、成熟。有些人或许对亲情不以为然，认为爱情和亲情是两回事，如果两个人之间只
有亲情没有爱情，那就没什么意思了。凡事不能太过，只有亲情没有爱情当然不好，但
亲情与爱情绝对不是相互排斥的，爱情发展、成熟、升华成为爱情和亲情水乳交融的状
态，你我是一家人，利益共同体，不可分割、不分你我的家人，才是高境界的、实在的
、能经得起考验的、可长久的爱情。
英国80年代有个很出名的乐队，男女主唱是相爱的恋人，但后来闹别扭，两个人分开了
。此后不久男的查出癌症，女的立马回到他身边，陪伴他渡过他人生最困难的一段时光
。当男的病情好转之后，女的才又正式离开了他，两个人又重新开始了自己的生活。二
十年后，电视采访这个男歌手，他说两个人相爱，不仅仅是爱情，还会发展出亲情，像
一家人一样，虽然两人闹翻，但当你看到你的家人命悬一线，你不会坐视不管，你一定
会义无反顾的尽你一切力量去帮助你的家人。所以爱情发展出亲情，不是中华文明圈的
专利，西方现代文明里也有类似元素，人类思想、情感、文化都是相通的。
要说琼瑶奶奶也真是的，和老公也好了五十年了，他一个病人，不认你了，这又怎么样
？难道他就不是你的家人吗？你还关心他、爱护他，这不就够了吗，他不知道又如何？
！他也没几天活了，难道这点小委屈，你都受不了吗？不是说过爱一个人要义无反顾，
不计得失吗？！看来爱情没发展、成熟、升华到与亲情水乳交融的境界，好了五十年也
经不起考验！

h*e2017-05-07 07:05

4 楼

典型动态规划。。。。。应该还有加速方法，如果你没学过动态规划做出来了，那就是高手；如果学过了，还用提示，有点说不过去

M*a2017-05-07 07:05

5 楼

人家老公自己要求在没意识时,要爱乐死的

r*u2017-05-07 07:05

6 楼

k=2还好, k>2感觉挺复杂的,你怎么做的?

【在 E********a 的大作中提到】

: 一个数组，N个正整数，分成x段，找一种分段法，minimize the maximum sum of x
: pieces,
: i.e.,
: minimize: MAX OF {sum of piece_1, sum of piece_2, ..., sum of piece_X}
: 大家觉得这个题目如果用了很多提示，最后能做出来，是不是还不错了？

a*n2017-05-07 07:05

7 楼

又见这道题 binary search

f*g2017-05-07 07:05

8 楼

能给个Link吗

【在 a****n 的大作中提到】

: 又见这道题 binary search

E*a2017-05-07 07:05

9 楼

如果没学过，或者忘了动态规划，遇到这样的题，面试人给了很多提示，勉强能做出来
的话，还算是可以的了？

就是高手；如果学过了，还用提示，
有点说不过去

【在 h********e 的大作中提到】

: 典型动态规划。。。。。应该还有加速方法，如果你没学过动态规划做出来了，那就是高手；如果学过了，还用提示，有点说不过去

a*12017-05-07 07:05

10 楼

就怕人假设你应该知道动态规划阿
你递归的？

【在 E********a 的大作中提到】

: 如果没学过，或者忘了动态规划，遇到这样的题，面试人给了很多提示，勉强能做出来
: 的话，还算是可以的了？
:
: 就是高手；如果学过了，还用提示，
: 有点说不过去

E*a2017-05-07 07:05

11 楼

我觉得，interviewer是假设candidate可能知道dp，也可能不知道，关系不大。
interviewer希望看到candidate不知道
dp的时候，在一步一步给出提示的情况下，如何找更优的解法？
candidate用了一些提示，想出递归的算法，但是进一步优化到多项式复杂度的过程比
较费力

【在 a********1 的大作中提到】

: 就怕人假设你应该知道动态规划阿
: 你递归的？

z*n2017-05-07 07:05

12 楼

任何时候，经提示做出应该都是最好的结果，我个人认为比直接做出效果更好。面试不
是找做题机器，而是找以后能一起相处工作的人。工作时候遇到不会的最直接的就是同
事讨论，让面试官觉得你是一个让人愿意愉快进行讨论并且能讨论出结果的人，无疑比
做题本身更加重要。会想你中学时候，是不是有的人你愿意跟他讨论问题，有的人你不
愿意？想想你愿意跟哪种人共事就知道了

【在 E********a 的大作中提到】

: 如果没学过，或者忘了动态规划，遇到这样的题，面试人给了很多提示，勉强能做出来
: 的话，还算是可以的了？
:
: 就是高手；如果学过了，还用提示，
: 有点说不过去

a*n2017-05-07 07:05

13 楼

0 < sum of piece < sum all, 在这个区间进行二分
http://poj.org/problem?id=3273
http://poj.org/bbs?problem_id=3273

h*e2017-05-07 07:05

14 楼

啊。。我没认真看题目。。应该是二分。。不是那种一个字串砍k段，让求最大和

w*92017-05-07 07:05

15 楼

好巧妙的运用二分啊

【在 a****n 的大作中提到】

: 0 < sum of piece < sum all, 在这个区间进行二分
: http://poj.org/problem?id=3273
: http://poj.org/bbs?problem_id=3273

d*f2017-05-07 07:05

16 楼

不明白题目的意思,能给个例子吗?

【在 E********a 的大作中提到】

: 一个数组，N个正整数，分成x段，找一种分段法，minimize the maximum sum of x
: pieces,
: i.e.,
: minimize: MAX OF {sum of piece_1, sum of piece_2, ..., sum of piece_X}
: 大家觉得这个题目如果用了很多提示，最后能做出来，是不是还不错了？

h*e2017-05-07 07:05

17 楼

其实这题DP也不是一无是处。。。如果数字及其长的话，DP速度比二分快。二分的速度
基本是log^2(所有数字和)*n, DP是2nklog和。

w*g2017-05-07 07:05

18 楼

动态规划, 基本题. 这种题目出了就是为了考动态规划. 动态规划用递归解也是可以的
, 但是不符合套路, 需要扣分. 如果给出指数时间的递归那肯定毙掉 -- 如果是我是面
试官的话.

【在 E********a 的大作中提到】

: 一个数组，N个正整数，分成x段，找一种分段法，minimize the maximum sum of x
: pieces,
: i.e.,
: minimize: MAX OF {sum of piece_1, sum of piece_2, ..., sum of piece_X}
: 大家觉得这个题目如果用了很多提示，最后能做出来，是不是还不错了？

E*a2017-05-07 07:05

19 楼

我不是想考dp，如果candidate懂dp，我想看他们能不能做到log加速，如果candidate
不会dp，我想看他们能不能在我
给提示告诉他dp思想的情况下做出dp的解法。
btw，我是interviewer。

【在 w***g 的大作中提到】

: 动态规划, 基本题. 这种题目出了就是为了考动态规划. 动态规划用递归解也是可以的
: , 但是不符合套路, 需要扣分. 如果给出指数时间的递归那肯定毙掉 -- 如果是我是面
: 试官的话.

a*n2017-05-07 07:05

20 楼

现在招人搞得跟竞赛似的,对实际项目上的东西没一点帮助
招个senior level developer, 人家15年工作经验, 还要考算法,

h*e2017-05-07 07:05

21 楼

这玩意儿就是考考基本功。。竞赛题比这些难多了。。这题目出到竞赛去所有的人都得
做出来了

a*n2017-05-07 07:05

22 楼

DP你做项目用的到么？

h*k2017-05-07 07:05

23 楼

DP的话怎么做？

E*a2017-05-07 07:05

24 楼

此言诧异了。
比如我出这个题，我的bar是看candidate的相对表现的，相对他自己的knowledge
scope：
如果他不熟悉DP，那么我的bar是，我给提示给思路，希望candidate能够利用这些提示
顺利的解决这个
问题，写出clean的code，我也就很满意了。
DP本来也不是啥高深的东西，无非就是一个解决问题的思路：cache计算结果避免重复
计算而已。你可以
完全没听说过状态转移方程，最优子结构，如果你有不错的analytic problem solving
能力的话，有
了这些提示，应该是能做出来的。而你这个从不会到会的学习和领悟的能力，才是我考
察的。
如果candidate很熟悉DP，那么我希望他能找到优化方案，我希望看他的思考能力，如
何去优化，从什么
地方入手想，当然，我也可以给一些log加速的提示。
如果candidate很熟悉DP，也知道log加速方案，我很高兴，但是我会继续move on到下
一个问题。

【在 a****n 的大作中提到】

: 现在招人搞得跟竞赛似的,对实际项目上的东西没一点帮助
: 招个senior level developer, 人家15年工作经验, 还要考算法,

a*n2017-05-07 07:05

25 楼

不是高深不高深的问题，实际项目多半用不上这些东西。招人是做项目，不是做题。
问算法还不如问问他读过哪些书。
我自己也在国内的一个外企写过几年程序，有些职位根本发挥不了你的能力，就是实现feature，连high level design都是写好的。一个师兄 topcoder 2186, 4年前去的MS，一直没涨级，今年年初去google了，你能力好怎么了，你所处的位置决定你做什么，项目可能根本用不到你的能力。
MS里面大多数人在SDE2位置待5年以上，如果你能力很强，而且很能说，还要看你做的项目以及和MANAGER的关系，哪个公司都是这样。AMAZON 的SDE2 到senior更难升级。

E*a2017-05-07 07:05

26 楼

我主要的意思是，问算法coding题的目的，是想找头脑灵活善于思考解决问题，而且有扎实编程基础的
人，因为这样的人做项目时能很快上手，能做好项目，我也希望与这样的人共同工作讨论问题。
即便是有几年经验的人，我觉得善于思考解决问题这一点仍然是很重要的，因为他的经验很可能用不
上，就算他的职位跟经验match，他以后换组呢，以后遇到他没经历过的问题呢? 况且我们这里是
general hiring，candidate以后来什么组都还不知道，所以除非是candidate特别擅长某类
领域，in general我们希望招解决问题能力强的人，做什么都能上手。
问算法题，其实只是一个手段。虽然说，有的时候，是不太容易做出公平的评价，对于一个头脑灵
活的人面试的时候因为紧张或者想偏了等原因没发挥好 vs 一个因为做了充分准备和练习/做过原题而
发挥好的人。
TC2186去MS是可惜了，好歹也去个FB啥的，现在不就爽了。

i*e2017-05-07 07:05

27 楼

我觉得算法固然重要，但是如果你聘请一个人完全取决于他的算法能力，那也太说不过
去了。
我觉得一个好的程序员除了需要有很好的problem solving，更重要的是他对你们公司
做的项目到底感不敢兴趣，有没有热忱。就算有幸给你聘请到，如果他天天来上班对你
们做的项目不感兴趣，那这是公司要请的人吗？
况且，一来就给面试者出DP题，我觉得作为面试题也太过了。毕竟DP题不是很多人懂，
而且要有DP的思路是需要经过不断的练习和总结才训练出来的。要知道身为面试的人会
比平时紧张，思路很容易就不清楚，然后陷入更紧张的状态。
我觉得一个好的面试题应该是有多种解法的。可以很容易想到brute force的解法，但
是也有不那么明显的方法来优化。可以先让面试者以brute force写代码（brute force
的代码不一定都很直接，也有存在很多陷阱，不容易写对的情况）。这时候面试者已经
放松一些了，才更深入地问怎么优化等等。这样我觉得能让面试者比较正常发挥自己的
水平。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

solving

【在 E********a 的大作中提到】

: 此言诧异了。
: 比如我出这个题，我的bar是看candidate的相对表现的，相对他自己的knowledge
: scope：
: 如果他不熟悉DP，那么我的bar是，我给提示给思路，希望candidate能够利用这些提示
: 顺利的解决这个
: 问题，写出clean的code，我也就很满意了。
: DP本来也不是啥高深的东西，无非就是一个解决问题的思路：cache计算结果避免重复
: 计算而已。你可以
: 完全没听说过状态转移方程，最优子结构，如果你有不错的analytic problem solving
: 能力的话，有

a*n2017-05-07 07:05

28 楼

算法问题就是的准备，即使有工作经验的也需要大量时间准备算法，而不是我项目做的
好，我算法也会很好。现在像MS，GOOGLE，AMAZON这类公司不可能只问一些基本算法和
数据结构。
ANYWAY反正我算法不好，也不想准备，跟这类公司是没啥缘分。

有扎实编程基础的
讨论问题。
经验很可能用不
且我们这里是
长某类
对于一个头脑灵
练习/做过原题而

【在 E********a 的大作中提到】

: 我主要的意思是，问算法coding题的目的，是想找头脑灵活善于思考解决问题，而且有扎实编程基础的
: 人，因为这样的人做项目时能很快上手，能做好项目，我也希望与这样的人共同工作讨论问题。
: 即便是有几年经验的人，我觉得善于思考解决问题这一点仍然是很重要的，因为他的经验很可能用不
: 上，就算他的职位跟经验match，他以后换组呢，以后遇到他没经历过的问题呢? 况且我们这里是
: general hiring，candidate以后来什么组都还不知道，所以除非是candidate特别擅长某类
: 领域，in general我们希望招解决问题能力强的人，做什么都能上手。
: 问算法题，其实只是一个手段。虽然说，有的时候，是不太容易做出公平的评价，对于一个头脑灵
: 活的人面试的时候因为紧张或者想偏了等原因没发挥好 vs 一个因为做了充分准备和练习/做过原题而
: 发挥好的人。
: TC2186去MS是可惜了，好歹也去个FB啥的，现在不就爽了。

r*92017-05-07 07:05

29 楼

怎么个log加速法？

candidate

【在 E********a 的大作中提到】

: 我不是想考dp，如果candidate懂dp，我想看他们能不能做到log加速，如果candidate
: 不会dp，我想看他们能不能在我
: 给提示告诉他dp思想的情况下做出dp的解法。
: btw，我是interviewer。

g*s2017-05-07 07:05

30 楼

算法真正的掌握是让它变成你思考的一个方法，而不是死记。
就像贪心，其实没学过算法的人很多也能直接想到贪心。
动态规划也一样，变成你的思想的时候，就算10年没做，回来还是能马上pickup。

【在 a****n 的大作中提到】

: 算法问题就是的准备，即使有工作经验的也需要大量时间准备算法，而不是我项目做的
: 好，我算法也会很好。现在像MS，GOOGLE，AMAZON这类公司不可能只问一些基本算法和
: 数据结构。
: ANYWAY反正我算法不好，也不想准备，跟这类公司是没啥缘分。
:
: 有扎实编程基础的
: 讨论问题。
: 经验很可能用不
: 且我们这里是
: 长某类

d*l2017-05-07 07:05

31 楼

我认为在状态转移的时候，要找max(dp[i-k][j-1], sum[i]-sum[i-k])中的最小值，而
这个随k的变化是一个单峰函数，只有一个极小值点（可能有俩，细节还需商榷）。而
找单峰函数的极值是可以用三分还是某种方法用log的复杂度找到的

【在 r********9 的大作中提到】

: 怎么个log加速法？
:
: candidate

c*m2017-05-07 07:05

32 楼

?
你怎么状态划分的?
.

【在 h********e 的大作中提到】

: 其实这题DP也不是一无是处。。。如果数字及其长的话，DP速度比二分快。二分的速度
: 基本是log^2(所有数字和)*n, DP是2nklog和。

g*s2017-05-07 07:05

33 楼

你说的有道理。但是你要意识到不同的人思维和学习方式不同。
有的人反应快，上手快。但也有人反应慢一些，但想的深，有后劲。现在这种面试方式
，基本上就是当
年搞竞赛那一套，比反应快，或者做题多。这种情况工作过的人哪里比的过刚毕业的小
年轻们？

有扎实编程基础
的
讨论问题。
经验很可能用不
且我们这里是
长某类
对于一个头脑灵
练习/做过原题
而

【在 E********a 的大作中提到】

: 我主要的意思是，问算法coding题的目的，是想找头脑灵活善于思考解决问题，而且有扎实编程基础的
: 人，因为这样的人做项目时能很快上手，能做好项目，我也希望与这样的人共同工作讨论问题。
: 即便是有几年经验的人，我觉得善于思考解决问题这一点仍然是很重要的，因为他的经验很可能用不
: 上，就算他的职位跟经验match，他以后换组呢，以后遇到他没经历过的问题呢? 况且我们这里是
: general hiring，candidate以后来什么组都还不知道，所以除非是candidate特别擅长某类
: 领域，in general我们希望招解决问题能力强的人，做什么都能上手。
: 问算法题，其实只是一个手段。虽然说，有的时候，是不太容易做出公平的评价，对于一个头脑灵
: 活的人面试的时候因为紧张或者想偏了等原因没发挥好 vs 一个因为做了充分准备和练习/做过原题而
: 发挥好的人。
: TC2186去MS是可惜了，好歹也去个FB啥的，现在不就爽了。

a*n2017-05-07 07:05

34 楼

这个题最佳的解法就是二分法，而且大多数面试官也不知道这个方法。

【在 g***s 的大作中提到】

: 算法真正的掌握是让它变成你思考的一个方法，而不是死记。
: 就像贪心，其实没学过算法的人很多也能直接想到贪心。
: 动态规划也一样，变成你的思想的时候，就算10年没做，回来还是能马上pickup。

g*s2017-05-07 07:05

35 楼

二分的速度can be polished to O( nlogn + nlog(max of 所有数字) )
DP could be O(nklogn)

【在 h********e 的大作中提到】

: 其实这题DP也不是一无是处。。。如果数字及其长的话，DP速度比二分快。二分的速度
: 基本是log^2(所有数字和)*n, DP是2nklog和。

d*l2017-05-07 07:05

36 楼

问一下，这题dp的优化是靠在状态转移时用找单峰函数极值的方法么？
这题二分确实更好，其实这种二分答案的方法还是很常见的，不过对有些题只能用dp

【在 g***s 的大作中提到】

: 二分的速度can be polished to O( nlogn + nlog(max of 所有数字) )
: DP could be O(nklogn)

g*s2017-05-07 07:05

37 楼

yes. you alredy gave the answer in your previous post. :)

【在 d*******l 的大作中提到】

: 问一下，这题dp的优化是靠在状态转移时用找单峰函数极值的方法么？
: 这题二分确实更好，其实这种二分答案的方法还是很常见的，不过对有些题只能用dp

h*o2017-05-07 07:05

38 楼

这两个问题还是有区别的
在你提供的链接里的这个问题中，顺序是定的。
当k = 2是，
如输入
3，2，2，1
则二分输出 5， {[3, 2], [2, 1]}
如输入
1，3，2，2
则二分输出 4, {[1, 3], [2, 2]}
搂主的问题是找到无序的情况下的最小值

【在 a****n 的大作中提到】

: 0 < sum of piece < sum all, 在这个区间进行二分
: http://poj.org/problem?id=3273
: http://poj.org/bbs?problem_id=3273

h*o2017-05-07 07:05

39 楼

请问楼主具体解法是什么呢？
这个问题和Multiprocessor scheduling应该是一样的
http://en.wikipedia.org/wiki/Multiprocessor_scheduling
给出approximate algorithm的比较多

solving

【在 E********a 的大作中提到】

: 此言诧异了。
: 比如我出这个题，我的bar是看candidate的相对表现的，相对他自己的knowledge
: scope：
: 如果他不熟悉DP，那么我的bar是，我给提示给思路，希望candidate能够利用这些提示
: 顺利的解决这个
: 问题，写出clean的code，我也就很满意了。
: DP本来也不是啥高深的东西，无非就是一个解决问题的思路：cache计算结果避免重复
: 计算而已。你可以
: 完全没听说过状态转移方程，最优子结构，如果你有不错的analytic problem solving
: 能力的话，有

i*e2017-05-07 07:05

40 楼

高手请指教，DP 我能想到的是 O(kN^2)，怎么优化成 O（NklogN）呢？
我的思路在这里:
http://www.ihas1337code.com/2011/04/the-painters-partition-prob
利用 Binary Search 的二分搜索，复杂度应该是 O(N log ( Sum of(A) ) 才对吧？不
对请指正一下，谢谢。
我的二分思路在这里：
http://www.ihas1337code.com/2011/04/the-painters-partition-prob

【在 g***s 的大作中提到】

: 二分的速度can be polished to O( nlogn + nlog(max of 所有数字) )
: DP could be O(nklogn)

g*s2017-05-07 07:05

41 楼

lz means order fixed.
pls notice he said "piece".

【在 h***o 的大作中提到】

: 这两个问题还是有区别的
: 在你提供的链接里的这个问题中，顺序是定的。
: 当k = 2是，
: 如输入
: 3，2，2，1
: 则二分输出 5， {[3, 2], [2, 1]}
: 如输入
: 1，3，2，2
: 则二分输出 4, {[1, 3], [2, 2]}
: 搂主的问题是找到无序的情况下的最小值

g*s2017-05-07 07:05

42 楼

sum(i)表示到第i个元素的和。O(n)可以做。
用二分对i来找到一个位置p，使得sum(p)可以满足题意，但sum(p-1)不能。 O(nlogn)
例如 2，2，2，2，2，5，5，5，1，1，1，1，1 k=3
那么这个p=5 sum(5)=10,sum(4）=8不行
然后对 sum（p-1) -> sum(p)进行二分。可以知道，sum(p)-sum(p-1)的值就是a[p]，
小于等
于max(a[])
所以，负责度是O(nlogn + n log max(a[])
对于DP，因为
dp[k-1][n] 对于n是一个单调递增的函数。我们用二分来找那个max就可以了。
所以是 O(NKLogN)
另外，空间复杂度可以用O(n)因为任何dp函数，k都只和dp[k-1]相关。所以，用两个长
度为n
的array就可以了。（另外还要一个sum（i）的数组，那么空间是3×n）

【在 i**********e 的大作中提到】

: 高手请指教，DP 我能想到的是 O(kN^2)，怎么优化成 O（NklogN）呢？
: 我的思路在这里:
: http://www.ihas1337code.com/2011/04/the-painters-partition-prob
: 利用 Binary Search 的二分搜索，复杂度应该是 O(N log ( Sum of(A) ) 才对吧？不
: 对请指正一下，谢谢。
: 我的二分思路在这里：
: http://www.ihas1337code.com/2011/04/the-painters-partition-prob

g*e2017-05-07 07:05

43 楼

学习

【在 g***s 的大作中提到】

: sum(i)表示到第i个元素的和。O(n)可以做。
: 用二分对i来找到一个位置p，使得sum(p)可以满足题意，但sum(p-1)不能。 O(nlogn)
: 例如 2，2，2，2，2，5，5，5，1，1，1，1，1 k=3
: 那么这个p=5 sum(5)=10,sum(4）=8不行
: 然后对 sum（p-1) -> sum(p)进行二分。可以知道，sum(p)-sum(p-1)的值就是a[p]，
: 小于等
: 于max(a[])
: 所以，负责度是O(nlogn + n log max(a[])
: 对于DP，因为
: dp[k-1][n] 对于n是一个单调递增的函数。我们用二分来找那个max就可以了。

g*e2017-05-07 07:05

44 楼

sum(p-1)->sum(p)二分怎么操作？倒着来?

？不

【在 g***s 的大作中提到】

: sum(i)表示到第i个元素的和。O(n)可以做。
: 用二分对i来找到一个位置p，使得sum(p)可以满足题意，但sum(p-1)不能。 O(nlogn)
: 例如 2，2，2，2，2，5，5，5，1，1，1，1，1 k=3
: 那么这个p=5 sum(5)=10,sum(4）=8不行
: 然后对 sum（p-1) -> sum(p)进行二分。可以知道，sum(p)-sum(p-1)的值就是a[p]，
: 小于等
: 于max(a[])
: 所以，负责度是O(nlogn + n log max(a[])
: 对于DP，因为
: dp[k-1][n] 对于n是一个单调递增的函数。我们用二分来找那个max就可以了。

g*s2017-05-07 07:05

45 楼

min=sum(p-1) 这个不满足
max=sum(p) 这个满足
这个范围里面有的数字就是max-min+1=a[p]+1

【在 g**e 的大作中提到】

: sum(p-1)->sum(p)二分怎么操作？倒着来?
:
: ？不

g*e2017-05-07 07:05

46 楼

明白了，这个比ihascode那个要高效。赞大牛

【在 g***s 的大作中提到】

: min=sum(p-1) 这个不满足
: max=sum(p) 这个满足
: 这个范围里面有的数字就是max-min+1=a[p]+1

i*e2017-05-07 07:05

47 楼

你的加速法非常巧妙，太好太强大，一定要狂赞！
非常感谢你，小弟学习了！
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 g***s 的大作中提到】

: sum(i)表示到第i个元素的和。O(n)可以做。
: 用二分对i来找到一个位置p，使得sum(p)可以满足题意，但sum(p-1)不能。 O(nlogn)
: 例如 2，2，2，2，2，5，5，5，1，1，1，1，1 k=3
: 那么这个p=5 sum(5)=10,sum(4）=8不行
: 然后对 sum（p-1) -> sum(p)进行二分。可以知道，sum(p)-sum(p-1)的值就是a[p]，
: 小于等
: 于max(a[])
: 所以，负责度是O(nlogn + n log max(a[])
: 对于DP，因为
: dp[k-1][n] 对于n是一个单调递增的函数。我们用二分来找那个max就可以了。

g*i2017-05-07 07:05

48 楼

没学过dp,就看过介绍,能详细说下你这里这个max()的意思吗?

【在 d*******l 的大作中提到】

: 我认为在状态转移的时候，要找max(dp[i-k][j-1], sum[i]-sum[i-k])中的最小值，而
: 这个随k的变化是一个单峰函数，只有一个极小值点（可能有俩，细节还需商榷）。而
: 找单峰函数的极值是可以用三分还是某种方法用log的复杂度找到的

g*y2017-05-07 07:05

49 楼

这个解法很好，但是跟DP没什么关系吧？
总结起来就是：
1. 用二分找到分割点p
2. 再用二分找出精确值，这个值在sum[p-1]和sum[p]之间

【在 g***s 的大作中提到】

: sum(i)表示到第i个元素的和。O(n)可以做。
: 用二分对i来找到一个位置p，使得sum(p)可以满足题意，但sum(p-1)不能。 O(nlogn)
: 例如 2，2，2，2，2，5，5，5，1，1，1，1，1 k=3
: 那么这个p=5 sum(5)=10,sum(4）=8不行
: 然后对 sum（p-1) -> sum(p)进行二分。可以知道，sum(p)-sum(p-1)的值就是a[p]，
: 小于等
: 于max(a[])
: 所以，负责度是O(nlogn + n log max(a[])
: 对于DP，因为
: dp[k-1][n] 对于n是一个单调递增的函数。我们用二分来找那个max就可以了。

i*e2017-05-07 07:05

50 楼

max() 是函数 maximum 的意思，就是两个值的比较，返回较大的那个值。
max(a,b) = a --> if (a > b)
else
max(a,b) = b
而递归的公式是：
M[n, k] = min { max (from j=1..n) { M[j, k-1], ∑(i=j..n-1) Ai } }
如果利用以上公式硬递归的话，就会非常慢，所以用 dp 来优化。可以顺序渐进，将计
算结果储存在数组里，这样就不用反复计算 M[j, k-1] 的值。其实主要思路还是怎么
获得这个公式，获得了之后用 dp 来优化就很直观了。
更多有关 dp 的思路请看这里：
http://www.ihas1337code.com/2011/04/the-painters-partition-prob

【在 g*****i 的大作中提到】

: 没学过dp,就看过介绍,能详细说下你这里这个max()的意思吗?

g*s2017-05-07 07:05

51 楼

DP is another algo to solve this question.

【在 g**********y 的大作中提到】

: 这个解法很好，但是跟DP没什么关系吧？
: 总结起来就是：
: 1. 用二分找到分割点p
: 2. 再用二分找出精确值，这个值在sum[p-1]和sum[p]之间

d*e2017-05-07 07:05

52 楼

sum(i)表示到第i个元素的和。O(n)可以做。
nlogn)
────────
可以解释一下什么是满足题意吗？是说sum(p) = maximum吗？如果大数字都在队尾，p
可能不存在。
Number array: 1, 1, 10 k=2
p = ?

g*e2017-05-07 07:05

53 楼

p=3

p

【在 d*****e 的大作中提到】

: sum(i)表示到第i个元素的和。O(n)可以做。
: nlogn)
: ────────
: 可以解释一下什么是满足题意吗？是说sum(p) = maximum吗？如果大数字都在队尾，p
: 可能不存在。
: Number array: 1, 1, 10 k=2
: p = ?

d*e2017-05-07 07:05

54 楼

if p=3, then the array has only one piece, which is smaller than k (2). How
to explain it has satisfied the requirement?

g*s2017-05-07 07:05

55 楼

of coz it does. you let one guy to do everyting and the other just take a
rest. but it is not the optimal answer.
so, we now know, sum(3) = 12 OK sum(2) = 2 Not OK
search between 2 and 12 using bi-search to find the correct answer, and
you will get it is 10.

How

【在 d*****e 的大作中提到】

: if p=3, then the array has only one piece, which is smaller than k (2). How
: to explain it has satisfied the requirement?

d*e2017-05-07 07:05

56 楼

Thanks for the explanation. It makes sense.

g*i2017-05-07 07:05

57 楼

谢谢解释,你的网站很好,这题的子问题我想不出来,你的网站解释的很好.不过你的算法
复杂度是kn^2,对O(nklogn)的dp算法我还是有写不明白:
max(dp[i-k][j-1], sum[i]-sum[i-k]) 如何看出是基于k的单峰函数?网上说单峰函数
判断用求导,谁能解释下?
单峰函数求极值我搜了一篇文章
http://hi.baidu.com/kyno_yang/blog/item/938a912dd0e3e3e58a1399c
类似log加速,前面说的3分法应该也是这样的吧,不过关键是要先判断出是单峰函数.
总之单峰函数以前没处理过,有点意思啊.

【在 i**********e 的大作中提到】

: max() 是函数 maximum 的意思，就是两个值的比较，返回较大的那个值。
: max(a,b) = a --> if (a > b)
: else
: max(a,b) = b
: 而递归的公式是：
: M[n, k] = min { max (from j=1..n) { M[j, k-1], ∑(i=j..n-1) Ai } }
: 如果利用以上公式硬递归的话，就会非常慢，所以用 dp 来优化。可以顺序渐进，将计
: 算结果储存在数组里，这样就不用反复计算 M[j, k-1] 的值。其实主要思路还是怎么
: 获得这个公式，获得了之后用 dp 来优化就很直观了。
: 更多有关 dp 的思路请看这里：

i*e2017-05-07 07:05

58 楼

恩
虽然明白了 grass 的二分优化法
但是也不知道怎么处理单峰函数
希望 grass 能展开说说
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 g*****i 的大作中提到】

: 谢谢解释,你的网站很好,这题的子问题我想不出来,你的网站解释的很好.不过你的算法
: 复杂度是kn^2,对O(nklogn)的dp算法我还是有写不明白:
: max(dp[i-k][j-1], sum[i]-sum[i-k]) 如何看出是基于k的单峰函数?网上说单峰函数
: 判断用求导,谁能解释下?
: 单峰函数求极值我搜了一篇文章
: http://hi.baidu.com/kyno_yang/blog/item/938a912dd0e3e3e58a1399c
: 类似log加速,前面说的3分法应该也是这样的吧,不过关键是要先判断出是单峰函数.
: 总之单峰函数以前没处理过,有点意思啊.

r*t2017-05-07 07:05

59 楼

dp[i-k][j-1]随k单调下降，sum[i]-sum[i-k]随k单调上升，画两条单增和单减的线取
max一定是单峰（其实应该是单谷），峰在两线相交处。

【在 g*****i 的大作中提到】

: 谢谢解释,你的网站很好,这题的子问题我想不出来,你的网站解释的很好.不过你的算法
: 复杂度是kn^2,对O(nklogn)的dp算法我还是有写不明白:
: max(dp[i-k][j-1], sum[i]-sum[i-k]) 如何看出是基于k的单峰函数?网上说单峰函数
: 判断用求导,谁能解释下?
: 单峰函数求极值我搜了一篇文章
: http://hi.baidu.com/kyno_yang/blog/item/938a912dd0e3e3e58a1399c
: 类似log加速,前面说的3分法应该也是这样的吧,不过关键是要先判断出是单峰函数.
: 总之单峰函数以前没处理过,有点意思啊.

g*i2017-05-07 07:05

60 楼

多谢解释!

【在 r*******t 的大作中提到】

: dp[i-k][j-1]随k单调下降，sum[i]-sum[i-k]随k单调上升，画两条单增和单减的线取
: max一定是单峰（其实应该是单谷），峰在两线相交处。

s*y2017-05-07 07:05

61 楼

刚看了一下1337 code上面这题的update，用了grass的优化
Using the above example:
A = { 100, 200, 300, 400, 500, 600, 700, 800, 900 }, and k = 3.
We build the cumulative array B:
B = { 100, 300, 600, 1000, 1500, 2100, 2800, 3600, 4500 }
After we apply binary search, we are able to find that B[4] = 1500, B[5] =
2100, because for costmax = 1500, x = 4; while costmax = 2100, x =3.
这里我们用这个2分找到lo是1500
那么为什么不可以直接用最大的sum/worker = 4500/3 = 1500 当为我们的lo呢？
如果1500不在sum array里面，我们最多也就是算比1500小的一个sum和比1500大的一个
sum需要的worker数目。
这样做有什么问题吗？
请指教。

【在 g***s 的大作中提到】

: min=sum(p-1) 这个不满足
: max=sum(p) 这个满足
: 这个范围里面有的数字就是max-min+1=a[p]+1

s*y2017-05-07 07:05

62 楼

顶一个。
刚看了一下1337 code上面这题的update，用了grass的优化
Using the above example:
A = { 100, 200, 300, 400, 500, 600, 700, 800, 900 }, and k = 3.
We build the cumulative array B:
B = { 100, 300, 600, 1000, 1500, 2100, 2800, 3600, 4500 }
After we apply binary search, we are able to find that B[4] = 1500, B[5] =
2100, because for costmax = 1500, x = 4; while costmax = 2100, x =3.
这里我们用这个2分找到lo是1500
那么为什么不可以直接用最大的sum/worker = 4500/3 = 1500 当为我们的lo呢？
如果1500不在sum array里面，我们最多也就是算比1500小的一个sum和比1500大的一个
sum需要的worker数目。
这样做有什么问题吗？
请指教。

【在 s*****y 的大作中提到】

: 刚看了一下1337 code上面这题的update，用了grass的优化
: Using the above example:
: A = { 100, 200, 300, 400, 500, 600, 700, 800, 900 }, and k = 3.
: We build the cumulative array B:
: B = { 100, 300, 600, 1000, 1500, 2100, 2800, 3600, 4500 }
: After we apply binary search, we are able to find that B[4] = 1500, B[5] =
: 2100, because for costmax = 1500, x = 4; while costmax = 2100, x =3.
: 这里我们用这个2分找到lo是1500
: 那么为什么不可以直接用最大的sum/worker = 4500/3 = 1500 当为我们的lo呢？
: 如果1500不在sum array里面，我们最多也就是算比1500小的一个sum和比1500大的一个

k*n2017-05-07 07:05

63 楼

你是什么公司的？

solving

【在 E********a 的大作中提到】

: 此言诧异了。
: 比如我出这个题，我的bar是看candidate的相对表现的，相对他自己的knowledge
: scope：
: 如果他不熟悉DP，那么我的bar是，我给提示给思路，希望candidate能够利用这些提示
: 顺利的解决这个
: 问题，写出clean的code，我也就很满意了。
: DP本来也不是啥高深的东西，无非就是一个解决问题的思路：cache计算结果避免重复
: 计算而已。你可以
: 完全没听说过状态转移方程，最优子结构，如果你有不错的analytic problem solving
: 能力的话，有

g*s2017-05-07 07:05

64 楼

yes. you can.
So, you can skip all sum(i) < sum(n)/k. in your case, 100,300,600,1000.
but we still need to use binary search to check sum[4] to sum[8]. it
could be still O(nlogn).
But in the following case, it can get much improvement by your changes:
O(n) for this step.
1,1,1,1,1,1......,1, 10000, 10000 k=3

s*y2017-05-07 07:05

65 楼

Thanks da niu for the conform.

【在 g***s 的大作中提到】

: yes. you can.
: So, you can skip all sum(i) < sum(n)/k. in your case, 100,300,600,1000.
: but we still need to use binary search to check sum[4] to sum[8]. it
: could be still O(nlogn).
: But in the following case, it can get much improvement by your changes:
: O(n) for this step.
: 1,1,1,1,1,1......,1, 10000, 10000 k=3