在 Python 中查找获取新鲜甜甜圈的最大组数的程序

假设我们有一个值 batchSize 和一个数组 group,其中 groups[i] 表示有一组 group[i] 客户将访问商店。所以有一家甜甜圈店可以按给定的batchSize批量烘焙甜甜圈。但他们有一个规则,在供应下一批甜甜圈之前,他们必须供应一批中的所有甜甜圈。每个顾客将得到一个甜甜圈。当一组人进入商店时,必须先为该组的所有顾客提供服务,然后才能对下一组进行发言。如果一组人都得到新鲜的甜甜圈,他们可能会很高兴。(换句话说,该组的第一个客户不接受最后一组留下的甜甜圈)。

我们可以重新排列组,最后我们必须在重新排列组后找到最大可能的快乐组数。

因此,如果输入类似于 batchSize = 4 groups = [2,1,8,4,3],那么输出将为 4,因为我们可以像 [8,4,2,3,1] 一样重新排列它们,所以首先,二、三、四组都很开心。我们可以为第一组制作两批甜甜圈,第二组制作一批,然后制作一批然后提供给第三组和第四组。

示例

让我们看下面的实现来更好地理解

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

以上是 在 Python 中查找获取新鲜甜甜圈的最大组数的程序 的全部内容, 来源链接: utcz.com/z/360056.html

回到顶部