algorithm - 编程开发人员招聘挑战问题

Question

一家软件公司有 N 个团队。第i^个团队有 B _i个员工，总预算为 A _i个货币单位。每个团队都必须在员工中平均分配预算。但对于某些团队来说，这是不可能的。因此，公司必须对其团队的预算进行修订。在一次修改中，要修改第i^个团队的预算，前 i 个团队的预算必须增加 1。您的任务是找到所需的最小修改次数，以便对于每个团队，他们的预算在员工是可能的。

示例案例：(A ₁ B ₁ )、(A ₂ B ₂ )、(A ₃ B ₃ )：(1 1)、(3 7)、(5 4)。

解决方案是4。初始预算(1,3,5) -> (2,4,5) -> (5,7,8)

标签： algorithmdynamicgreedy

Answer 1

给定的问题可以通过建设性的解决方案来解决。首先，让我们i ​​nc _i表示每个A _i增加的数量，这样总和 ( A _i + inc _i ) 可以在B _{i 个}员工中平均分配。这里要进行的两个观察是：

• ( A _i + inc _i ) mod B _i应该等于 0 以使数量平均分配
• inc _i <= inc _i-1，因为我们总是从索引 1 开始以前缀方式增加预算，因此不可能有inc _i > inc _i-1因为inc _i-1总是在inc _{i之前增加}

使用这两个观察，我们可以开始从右到左迭代给定数组，并且在每一步我们确定inc _i的值。inc _i的值应为 ( c * B _i - A _i )，其中c是最小整数值，使得c * B _i >= A _i并且 ( c * B _i - A _i ) >= inc _i+1可以在 O(1) 中计算的值，因为我们可以修改方程来估计c的值，-

• c >= (A _i / B _i )
• c >= (A _i + inc _i+1 ) / B _i

因此c = max (ceil(A _i / B _i ), ceil((A _i + inc _i+1 ) / B _i )

因此，给定解决方案的整体复杂度是O(n)，最终解决方案是inc ₁的值（假设 1-indexing）