将K资源公平地划分给N个人

Question

K圆圈上有一些点代表宝藏的位置.N人们想分享宝藏.您希望在所有这些中公平地划分宝藏,使得具有最大值的人与具有最小值的人之间的差异尽可能地最小.

• 他们都在圈子上采取连续的一组点.也就是说,他们不能拥有分割的宝藏.
• 必须分配所有的宝藏
• 每个宝藏应该只属于一个人.

例如,如图中所示,如果有4个宝藏和2个人,则最佳划分方式是

(6,10)和(11,3)=>相差2.

1 <= n <= 25

1 <= k <= 50

我该如何解决这个问题呢？我计划计算所有点的平均值并继续添加资源,直到它们小于每个人的平均值.但尽管很明显,它并不适用于所有情况.

如果有人投光,我会很高兴的.

Answer 1

假设我们将 x、y 固定为宝藏允许的最小最大值。我需要弄清楚我们是否可以在这些限制下找到解决方案。

为此，我需要遍历圆并创建 N 个线段，其总和在 x 和 y 之间。我可以通过动态规划来解决这个问题，如果我可以将 i 和 j 之间的元素分成 l ，其总和在 x 和 y 之间（见上文），则 a[i][j][l] = 1 。为了计算它，我们可以计算 a[i][j][l] = is_there_a_q_such_that(a[i][q - 1][l-1] == 1 and sum(q -> j) between x and y)。要处理圆，请查找覆盖足够元素的 n-1 段，并且剩余差异保留在 x 和 y 之间。

所以天真的解决方案是 O(total_sum^2) 选择 X 和 Y 加上 O(K^3) 迭代 i,j,l 和另一个 O(K) 来找到 aq 和另一个 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。我们可以使用二分查找来找到位于 x 和 y 之间的最接近的 t 和最远的 q。我们称它们为 low_q（最接近 j，最小总和）和 high_q（远离 j，最大总和）。如果 low_q < i 则间隔太小，因此值为 0。所以现在我们需要检查 max(high_q, i) 和 low_q 之间是否有 1。最大的目的是确保我们不会在区间之外寻找。为了进行检查，我们可以再次预先计算部分和来计算 out 间隔中有多少个 1。我们只需要在每个级别执行一次，因此它会被摊销 O(1)。所以，如果我们做的一切都是正确的，这将是 O(K^3 logK)。

我们前面还有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 之一的复杂性。

您可能还可以做其他事情，但我认为这对于您的限制来说已经足够快了。