algorithm - 将K资源公平分配给N个人

Question

圆上有 K 个点，代表宝藏的位置。 N 人想要分享宝藏。你想把财宝公平地分配给所有人，使得拥有最大值(value)的人和拥有最小值(value)的人之间的差异尽可能小。

• 他们都在圆上取一组连续的点。也就是说，他们 不能拥有分段宝物。
• 必须分配所有宝物
• 每一件宝物只能属于一个人。

比如图中有4个宝物和2个人，那么最优的划分方式就是

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

1 <= n <= 25

1 <= k <= 50

我该如何解决这个问题？我计划计算所有点的平均值并不断添加资源，直到它们小于每个人的平均值。但尽管很明显，它并非在所有情况下都有效。

如果有人提出一些建议，我会很高兴。

Answer 1

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

为此，我需要遍历圆并准确创建 N 段，总和介于 x 和 y 之间。 如果我可以将 i 和 j 之间的元素拆分为总和介于 x 和 y 之间的 l(见上文)，我可以通过动态规划解决这个问题，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) 找到 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。我们可以使用二进制搜索来找到允许我们在 x 和 y 之间的最近的 t 和最远的 q。我们称它们为 low_q(最接近 j，总和最小)和 high_q(远离 j，总和最大)。如果 low_q < i 则区间太小，因此值为 0。所以现在我们需要检查 max(high_q, i) 和 low_q 之间是否存在 1。 max 是为了确保我们不看区间之外。为了进行检查，我们可以再次预先计算部分和以计算出间隔中有多少个 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 是复杂性。

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