巧克力甜度
一道关于切巧克力的题。题目是给定一个数组（一板巧克力），数组里的每一个数字都表示其中一块的甜度。有n个人来分享这巧克力，需要切n-1刀。其他n-1个人会把甜度高的portion都拿走 剩下的留给你。问如何切割这块巧克力你自己尽可能能拿到最高的甜度。比如数组[3,2,3,1,4],3个人分，切成[3,2 |3,1 |4]，你能拿到最多的4。后来问了朋友，听说可以用二分答案来做？
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=499453
followup可能有：
如果最高的甜度是按照max而非sum
这题的剧本应该就是先问清题意，再简要说一下DP能怎么做，再来就直接开二分法，尝试把巧克力分成K分每一分都要超过一个猜测的Target，利口肆妖灵的反题
分享一下这题和反过来的利口肆衣领见过的几种包装方法：
1. 一片巧克力数组分成K块，数字代表甜度，第一个人会想拿最甜的一块，把他平分成一个状态使得第一个人拿到的总甜度是最小的，求第一人拿到的甜度
2. 一个必须依照数组顺序完成的工作，数字代表工作难易度，分成K天完工，尽可能把困难度最高的一天变得比较不累，求最累的一天的困难度
3. 一个数组代表一排的书，数字代表页数，现在必须把相邻的书分成K组放置到K台打印机，设置一个配置方法使得需要打印最多页数的机器打印最少页，求工作量最多的打印机需要打印的页数
4. 一个包裹数组，数字代表重量，依包裹排列顺序分成K批寄送，使得最重的一批重量最小，求最重一批重量（利口比赛刚出的）
一道关于切巧克力的题。题目是给定一个数组（一板巧克力），数组里的每一个数字都表示其中一块的甜度。有n个人来分享这巧克力，需要切n-1刀。其他n-1个人会把甜度高的portion都拿走 剩下的留给你。问如何切割这块巧克力你自己尽可能能拿到最高的甜度。比如数组[3,2,3,1,4],3个人分，切成[3,2 |3,1 |4]，你能拿到最多的4。后来问了朋友，听说可以用二分答案来做？
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=499453
followup可能有：
如果最高的甜度是按照max而非sum
这题的剧本应该就是先问清题意，再简要说一下DP能怎么做，再来就直接开二分法，尝试把巧克力分成K分每一分都要超过一个猜测的Target，利口肆妖灵的反题
分享一下这题和反过来的利口肆衣领见过的几种包装方法：
1. 一片巧克力数组分成K块，数字代表甜度，第一个人会想拿最甜的一块，把他平分成一个状态使得第一个人拿到的总甜度是最小的，求第一人拿到的甜度
2. 一个必须依照数组顺序完成的工作，数字代表工作难易度，分成K天完工，尽可能把困难度最高的一天变得比较不累，求最累的一天的困难度
3. 一个数组代表一排的书，数字代表页数，现在必须把相邻的书分成K组放置到K台打印机，设置一个配置方法使得需要打印最多页数的机器打印最少页，求工作量最多的打印机需要打印的页数
4. 一个包裹数组，数字代表重量，依包裹排列顺序分成K批寄送，使得最重的一批重量最小，求最重一批重量（利口比赛刚出的）
leetcode的原题是minimize the largest subarry sum, 这题刚好相反, maximize the smallest subarry sum. 这样还能用binary search? 如果是binary search largest sum,一旦元素和超过现在的binary search target value,我们可以就可以split. 但是如果是search smallest subarry sum, 即时超过也不能说明要split. 请问我这样想有什么问题?谢谢.
原题是猜一个数使每一片段都<=过这个数，至少可以分成n片
这题是猜一个数使每一片段都> =这个数，这少可以分成n片（或是找最小的一个数，让他无法分成n片）
利口1014，思路一模一样。
二分法找max load/最大甜度，使得分割刚好是N
