Pythonで新鮮なドーナツを取得するグループの最大数を見つけるためのプログラム

値batchSizeと配列グループがあり、groups [i]は、ショップにアクセスするgroups[i]顧客のグループがあることを示しているとします。したがって、指定されたbatchSizeのバッチでドーナツを焼くドーナツショップがあります。ただし、ルールが1つあります。次のバッチのドーナツを提供する前に、バッチのすべてのドーナツを提供する必要があります。そして、各顧客はちょうど1つのドーナツを受け取ります。グループが店に入るとき、次のグループに対処する前に、そのグループのすべての顧客にサービスを提供する必要があります。あるグループは、全員が新鮮なドーナツを手に入れれば幸せかもしれません。 （つまり、グループの最初の顧客は、最後のグループから残ったドーナツを受け入れません。）

グループを並べ替えることができます。最後に、グループを並べ替えた後、幸せなグループの可能な最大数を見つける必要があります。

したがって、入力がbatchSize =4 groups =[2,1,8,4,3]のようである場合、最初に[8,4,2,3,1]のように再配置できるため、出力は4になります。 2番目、3番目、4番目のグループは幸せです。最初のグループ用に2つのドーナツのバッチを作成し、2番目のグループ用に1つのバッチを作成してから、3番目のグループに1つ、4番目のグループに1つのバッチを提供できます。

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

• l：=グループ内のすべてのgの（g mod batchSize）のリスト

• count：=lの要素の頻度を含むマップ

• g：=0からbatchSizeまでの範囲のすべてのiのcount[i]のリスト

• 関数dp（）を定義します。これにはsm、t

  がかかります

• tの最大値が0と同じ場合、

  • 0を返す

• ans：=0

• arr：=t

• 0からbatchSize-1の範囲のkの場合、実行

  • arr [k]が0と同じ場合、

    • 次のイテレーションに行く

  • arr [k]：=arr [k]-1

  • ans：=ansとdpの最大値（（sm + k）mod batchSize、arr）

  • arr [k]：=arr [k] + 1

• ans +（smが0と同じ場合は1、それ以外の場合は0）

  を返します。

• メインメソッドからreturndp（0、g）

例

理解を深めるために、次の実装を見てみましょう

from collections import Counter
def solve(batchSize, groups):
   l = [g % batchSize for g in groups]
   count = Counter(l)
   g = [count[i] for i in range(batchSize)]

   def dp(sm, t):
      if max(t) == 0:
         return 0

      ans, arr = 0, list(t)
      for k in range(batchSize):
         if arr[k] == 0:
            continue
         arr[k] -= 1
         ans = max(ans, dp((sm + k) % batchSize, arr))
         arr[k] += 1
      return ans + (sm == 0)

   return dp(0, g)

batchSize = 4
groups = [2,1,8,4,3]
print(solve(batchSize, groups))

入力

4, [2,1,8,4,3]

出力

4