Pythonを使用してm個の花束を作るための最小日数を見つけるプログラム

numsと呼ばれる整数の配列があるとすると、さらに2つの値mとkがあります。今、私たちはm個の花束を作る必要があります。 1つの花束を作るには、庭から隣接するk個の花が必要です。ここでは、庭はn種類の花で構成されており、i番目の花はbloomDay[i]に咲きます。各花は1つの花束の中でのみ使用できます。庭からm個の花束を作るのに必要な最小日数を見つける必要があります。 m個の花束を作成できない場合は、-1を返します。

したがって、入力がbloomDay =[5,5,5,5,10,5,5] m =2 k =3のようである場合、2（m =2）の花束が必要であり、それぞれが必要であるため、出力は10になります。花が3つあります。

• 5日目以降：[x、x、x、x、_、x、x]、開花した最初の3つの花の花束を1つ作成できますが、別の花束を作成することはできません

• 10日目以降：[x、x、x、x、x、x、x]、これで2つの花束をさまざまな方法で作成できます。

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

• n：=bloomDayのサイズ

• m * k> nの場合、

  • -1を返す

• 関数possible（）を定義します。これにはx

  かかります

• カウント：=0、花束：=0

• BloomDayの各dについて、実行します

  • d <=xの場合、

    • count：=count + 1

    • countがkと同じ場合、

      • ブーケ：=ブーケ+ 1

      • カウント：=0

  • それ以外の場合

    • カウント：=0

• 花束がm以上の場合はtrueを返し、それ以外の場合はfalseを返します

• メインの方法から、次のようにします-

• 左：=0、右：=1+bloomDayの最大値

• 左<右、する

  • mid：=（左+右）/ 2

  • 可能であれば（mid）が真の場合、

    • 右：=半ば

  • それ以外の場合

    • 左：=半ば+ 1

• 可能であれば（左）が真の場合、

  • 左に戻る

• それ以外の場合は左+1を返します

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

例

def solve(bloomDay, m, k):
   n = len(bloomDay)
   if m * k > n:
      return -1
   def possible(x):
      count = 0
      bouquets = 0
      for d in bloomDay:
         if d <= x:
            count += 1
            if count == k:
               bouquets += 1
               count = 0
         else:
            count = 0
      return bouquets >= m
   left, right = 0, max(bloomDay) + 1
   while left < right:
      mid = (left + right)//2
      if possible(mid):
         right = mid
      else:
         left = mid + 1
   if possible(left):
      return left
   else:
      return left + 1
bloomDay = [5,5,5,5,10,5,5]
m = 2
k = 3
print(solve(bloomDay, m, k))

入力

[5,5,5,5,10,5,5], 2, 3

出力

10