数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会科学
时装研究
法律研究使用 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
104 次查看
