用 Python 编写程序，找出最多有几组顾客可以得到新鲜甜甜圈

pythonserver side programmingprogramming更新于 2025/12/14 5:00:17

假设我们有一个 batchSize 值和一个数组 group，其中 groups[i] 表示有一组 groups[i] 顾客会光顾这家商店。因此，有一家甜甜圈店，以给定的 batchSize 批量烘焙甜甜圈。但他们有一条规则，他们必须先供应完一批甜甜圈，然后再供应下一批甜甜圈。并且每位顾客只能得到一个甜甜圈。当一组顾客进入商店时，必须先为该组的所有顾客提供服务，然后再接待下一组顾客。如果他们都得到新鲜的甜甜圈，那么一个组可能会很高兴。 (换句话说，该组中的第一位顾客不会接受上一组顾客剩下的甜甜圈)。

我们可以重新排列这些组，最后我们必须在重新排列这些组之后找到最大可能的满意组数。

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

为了解决这个问题，我们将遵循以下步骤 −

l := 一个列表，其中包含 (g mod batchSize)，其中包含组中所有 g
count := 一个包含 l 元素频率的映射
g := 一个列表，其中包含从 0 到 batchSize 范围内的所有 i，其中包含 count[i]
定义一个函数 dp() 。这将需要 sm、t
如果 t 的最大值与 0 相同，则
- 返回 0
ans := 0
arr := t
对于范围为 0 到 batchSize - 1 的 k，执行
- 如果 arr[k] 与 0 相同，则
  - 进行下一次迭代
- arr[k] := arr[k] - 1
- ans := ans 的最大值和 dp((sm + k) mod batchSize, arr)
- arr[k] := arr[k] + 1
返回 ans +(如果 sm 与 0 相同则为 1，否则为 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))