圆圈上有K点，它们代表宝藏的位置。 N人们想分享宝藏。您希望将宝藏公平地分配在所有宝藏中，以使具有最大值的人和具有最小值的人之间的差异尽可能小。
不能拥有分割的宝藏。
例如，如图所示，如果有4个宝物和2个人，则最佳的划分方式是
(6，10)和(11，3)=>相差2。
我该如何解决这个问题？我计划计算所有点的均值，并继续添加资源，直到它们小于每个人的均值。但是，尽管很明显，它并非在所有情况下都有效。
如果有人给我点光，我会很高兴。
最佳答案
因此，说我们将x，y固定为该财宝所允许的最小最大值。
我需要弄清楚我们是否可以在这些约束条件下找到解决方案。
为此，我需要遍历圆并创建x和y之和的正好N个分段。
我可以通过动态编程解决a [i] [j] [l] = 1的问题，前提是我可以将i和j之间的元素拆分为l，它们的和在x和y之间(请参见上文)。为了计算它，我们可以评估a [i] [j] [l] = is_there_a_q_such_that(a [i] [q-1] [l-1] == 1且sum(q-> j)在x和y之间)。
要处理该圆，请查找覆盖足够元素的n-1个段，并且剩余的差值保持在x和y之间。
因此，天真的解决方案是O(total_sum ^ 2)来选择X和Y，再加上O(K ^ 3)来遍历i，j，l和另一个O(K)来找到q，另一个O(K)来获得和。总计为O(total_sum ^ 2 * K ^ 5)，这可能太慢了。
因此，我们需要大量计算总和。因此，让我们预先计算部分和数组sums [w] = sum(pos 0和pos w之间的元素)。因此，要获得q和j之间的和，您只需要计算sums [j]-sums [q-1]。这照顾到O(K)。
计算a [i] [j] [l]。
由于珍宝始终是正数，因此如果部分总和过小，我们需要增大间隔，如果总和过高，则需要缩小间隔。正弦，我们固定间隔的一侧(在j处)，我们只能移动q。我们可以使用二进制搜索来找到闭合t和最远的q，使我们位于x和y之间。我们称它们为low_q(最接近j，最小和)和high_q(远离j，最大和)。如果low_q
我们前面仍然有total_sum ^ 2。假设我们修复了X。如果对于给定的y，我们有一个解决方案，那么您也许还能找到一个较小的y，但它仍然有一个解决方案。如果找不到给定y的解，则将找不到较小值的解。因此，我们现在可以对y进行二进制搜索。
所以现在是O(total_sum * log(total_sum)* K ^ 3 * logK)。
如果sum(0-> i-1)> x，其他优化将不增加i。
您可能不想检查x> total_sum/K的值，因为这是理想的最小值。这应该抵消掉K之一就是复杂性。
您可能还可以做其他事情，但是我认为这对于您的约束来说已经足够快了。
关于algorithm - 将K资源公平分配给N个人，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/52183035/