在 Python 中可以找到具有不同类型项目的 K 大小组的最大数量的程序

假设我们有一个称为 counts 的数字列表，其中 counts[i] 表示类型为 i 的项目数。我们还有另一个值 k。我们必须找到我们可以找到的大小为 k 的组的最大数量，这样每个组必须具有不同类型的项目。

所以，如果输入像counts = [2, 3, 5, 3] k = 2，那么输出将是6，因为让四种类型的项分别用a、b、c、d表示。我们可以有以下 k = 2 的组，其中所有元素都是不同的类型：[(c, a), (b, a), (c, b), (c, b), (d, a), (d, a)]。

示例

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

def possible(counts, groups, k):
   required = groups * k
   for i in range(len(counts)):
      temp = min(counts[i], groups, required)
      required -= temp
      if required == 0:
         return True
   return False

def solve(counts, k):
   res = 0
   l = 0
   r = sum(counts)
   while l <= r:
      m = l + (r - l) // 2
      if possible(counts, m, k):
         l = m + 1
         res = max(res, m)
      else:
         r = m - 1
   return res

counts = [2, 3, 5, 3]
k = 2
print(solve(counts, k))

输入

[2, 3, 5, 3], 2

6