在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)]。

为了解决这个问题，我们将按照以下步骤进行−

定义一个函数possible()。这将需要counts、groups、k
required：= groups * k
对于i从0到counts的大小，执行以下操作
- temp：=counts[i]、groups和required的最小值
- required：= required – temp
- 如果required与0相同，则
  - 返回True
返回False
定义一个函数solve()。这将需要counts、k
res：= 0
l：= 0
r：= counts中所有元素的总和
当l<= r时执行以下操作
- m：= l + (r-l) // 2
- 如果possible(counts, m, k)为true，则
  - l：= m + 1
  - res：= res和m的最大值
- 否则，
  - r：= m – 1
返回res

例子

让我们看看以下实现，以便更好地理解−

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))