使用 Python 查找获得新鲜甜甜圈的最多组数的程序

假设我们有一个值 batchSize 和一个数组 group，其中 groups[i] 表示有一组 groups[i] 顾客将访问商店。所以有一家甜甜圈店，以给定的 batchSize 为单位烘焙甜甜圈。但他们有一个规则，他们必须在提供下一批甜甜圈之前提供完一批甜甜圈。每个顾客将得到一个甜甜圈。当一组进入商店时，必须在处理任何下一组之前为该组的所有顾客提供服务。如果所有成员都得到新鲜的甜甜圈，一个组可能会很开心。（换句话说，该组的第一位顾客不接受上一组剩余的甜甜圈。）

我们可以重新排列这些组，最后我们必须在重新排列这些组之后找到尽可能多的快乐组。

因此，如果输入为 batchSize = 4 groups = [2,1,8,4,3]，则输出将为 4，因为我们可以将它们重新排列为 [8,4,2,3,1]，因此第一、第二、第三和第四组都很高兴。我们可以为第一组制作两批甜甜圈，为第二组制作一批甜甜圈，制作一批然后提供给第三组，为第四组制作一批。

要解决这个问题，我们将遵循以下步骤 -

  • l := 一组包含所有组中 g 的（g mod batchSize）

  • count := 一个包含 l 元素频率的映射

  • g := 一个包含 range 0 到 batchSize 中所有 i 的 count[i] 的列表

  • 定义一个函数 dp()。它将使用 sm、t

  • 如果 t 的最大值与 0 相同，则

    • 返回 0

  • ans := 0

  • arr := t

  • 进行 0 到 batchSize - 1 的循环，执行

    • 如果 arr[k] 与 0 相同，则

      • 进行下一个迭代

    • arr[k] := arr[k] - 1

    • ans := ans 的最大值和 dp((sm + k) mod batchSize, arr)

    • arr[k] := arr[k] + 1

  • 返回 ans +(1 如果 sm 与 0 相同，否则为 0)

  • 从主方法返回 dp(0, g)

示例

让我们看以下实现，以获得更好的理解

from collections import Counter
def solve(batchSize, groups):
   l = [g % batchSize for g in groups]
   count = Counter(l)
   g = [count[i] for i in range(batchSize)]

   def dp(sm, t):
      if max(t) == 0:
         return 0

      ans, arr = 0, list(t)
      for k in range(batchSize):
         if arr[k] == 0:
            continue
         arr[k] -= 1
         ans = max(ans, dp((sm + k) % batchSize, arr))
         arr[k] += 1
      return ans + (sm == 0)

   return dp(0, g)

batchSize = 4
groups = [2,1,8,4,3]
print(solve(batchSize, groups))

输入

4, [2,1,8,4,3]

输出

4

上次更新：08-10-2021

104 次查看

启动你的 职业生涯

通过完成课程获得认证

开始
广告