Pythonでは、異なるタイプのアイテムを持つKサイズのグループの最大数を見つけるプログラムが可能です。

counts [i]がタイプiのアイテムの数を表す、countsと呼ばれる数のリストがあるとします。別の値kもあります。サイズkのグループの最大数を見つける必要があります。そのため、各グループには異なるタイプのアイテムが必要です。

したがって、入力がcounts =[2、3、5、3] k =2のような場合、4つのタイプのアイテムがそれぞれa、b、c、dで表されるため、出力は6になります。 k =2の次のグループを持つことができます。ここで、すべての要素は異なるタイプです：[（c、a）、（b、a）、（c、b）、（c、b）、（d、a）、 （d、a）]。

これを解決するには、次の手順に従います-

• 関数possible（）を定義します。これには、カウント、グループ、kが必要です
• 必須：=グループ* k
• 0からカウントのサイズまでの範囲のiについては、
  • temp：=最小カウント[i]、グループ、および必須
  • 必須：=必須-臨時雇用者
  • 必要な場合は0と同じで、
    • Trueを返す
• Falseを返す
• 関数solve（）を定義します。これには数えられます、k
• res：=0
• l：=0
• r：=カウントに存在するすべての要素の合計
• l <=rの場合、do
  • m：=l +（r --l）/2の床
  • 可能であれば（counts、m、k）が真の場合、
    • l：=m + 1
    • res：=resとmの最大値
  • それ以外の場合、
    • r：=m-1
• return 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