在 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