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 + floor((r - l) / 2)
    • 如果possible(counts, m, k)為真，則
      • 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))

輸入

[2, 3, 5, 3], 2

輸出

6

更新於：2021年10月19日

866 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始
廣告