巧克力甜度

magmag 发表于 2019-3-24 04:18
请问能解释下这个 l -1吗？我试了几种其它的条件都不行，的确要下限减一， 但是思路上我有点没想通，为啥 ...

首先要知道利口1014/410问的东西和这题很像但是不一样：
- 原题问的是把最大值尽可能变小，总共要K份
可以把他想成一个Bar Graph，每一个subarray sum是一个Bar，总共要至少K个Bar，而且最高的那个Bar不得超过二分法猜的 Target．二分法的过程中我们要尽可能的把那个Target压小，直到Target再小一格的话就达不到 K 个Bar了．使用左闭右开的二分法模板，最后left的数值是“符合条件的最小数字”，在这一题的条件就是至少要K个Bar，而每个Bar都不能超过猜测的Target ，所以left 会得到最小化的最大值．

- 这题问的是把最小值尽可能变大，总共要K份
同理，我们也把题目想成一个Bar Graph，每一个subarray sum 是一个Bar，总共至少K个Bar，而这一次我们要让所有的Bar都至少达标一个猜测的Target，这样Target就是Bar Graph的最小值．二分法的过程中我们要尽可能的把这个猜测的Target变大，直到再变大一格就没办法分成K份了．可是如果要把猜测的数值尽可能变大，就没办法直接套用左闭右开的二分法模板了．其他的二分法模板应该能解决，但我很任性就只想记一种模板，所以为何不把二分法确认的条件换一下？我们也可以去猜一个Target，要求每一个Bar 都要Target，但如果用了这个Target 就不足以分成K份了，找这个Target的最小值．也就是说：使用二分法会找到一个最小值的Target，虽然不能分成K份，但它已经小到再小一格就能分成K份了．使用左闭又开模板Left会得到这个Target，所以Left-1就刚刚好是能分成K份的最大化最小值．

如果对左闭右开的二分法模板不熟，推荐去看油管一个叫花花酱的播主特辑第五章，讲得让人茅塞顿开，一种二分法模板打遍天下．

请问我看有人提到要求优化到logn * logn，有什么思路么？

kaipeng21 发表于 2019-3-24 05:22
首先要知道利口1014/410问的东西和这题很像但是不一样：
- 原题问的是把最大值尽可能变小，总共要K份
...

很清楚，谢谢！油管视频也看了，体会了一晚上， 希望下次遇到变形题能想明白。

kaipeng21 发表于 2019-3-18 22:55
原题是猜一个数使每一片段都 =这个数，这少可以分成n片（或是找最小的一个数，让他无法分成n片）

****  ...

算法是对的，但是复杂度并不是lgN*lgN?

chenqidi 发表于 2019/03/25 13:51:47


算法是对的，但是复杂度并不是lgN*lgN?

LogN*logN是哪个帖子说的我想去看一下，我觉得这题用410的思路就是Nlog(sum(A)-min(A))啊，难道validation function 可以logN解决？

请问大家dp的话怎么做？谢谢啦

那贴里lgn*lgn应该是笔误吧，数组并不能排序，你没法在不遍历的情况下判断是否能validate一个分割。不太懂信息论，但感觉无法超越On的

关于双倍积分奖励算法题和系统设计题讨论的决定：

我们：
1. 希望能看到干货讨论；
2. 希望能看到好的代码（web端高级发帖模式下，@ 朋友右边的<> 可以选择多种代码）

版主 @14417335 负责审核加分，也请大家给好的回复加分 + 顶。
大家给30，我会跟进奖励30，double之；
大家给100，我也会跟进奖励100，double之。

很理解大家写代码、调试、写思路分析，很花时间。对于特别好的回复，还会有额外加分。

欢迎大家拿出好的题目讨论，选中了我会全站置顶。哪位同学起了好的题目/帖子，激发了干货讨论，也会获得一定的积分奖励。

欢迎大家踊跃参与。看到好的回复，也请大家顶一下，作为对别人积极参与讨论、热心分享的认可和鼓励。
其他可以获得双倍积分的题目：

在刷题版里选择高频题标签，链接:
https://www.1point3acres.com/bbs/forum.php?mod=forumdisplay&fid=84&filter=typeid&typeid=1019

大家看到LC没有的高频题，也请贴到刷题版里，又有大米又有赞。对于学弟学妹们也是功劳一件。举手之劳。谢谢大家的参与。

我记得这道题还有个条件是每块巧克力的甜度是1至k，关键思路应该是切完之后甜度最高的与甜度最低的之间之差应小于k。
然后用greedy做。
假设巧克力原来有A块，每块甜度为1至k，有n个人平分。
那么从第一刀开始，每一portion与平均数（sum（甜度）/ n）之间的差应该小于K。
以此类推。

这题是我实习面的题