在 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 Counterdef 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