Pythonで観覧車からの利益を最大化するために必要な最小回転を見つけるためのプログラム

4つのキャビンを備えた観覧車があり、各キャビンに4人の乗客を収容できるとします。ホイールは反時計回りに回転し、回転するたびに「実行」の金額がかかります。これで、n個のアイテムを含む配列「cust」ができました。各アイテムiは、i番目の回転の前に観覧車に入るのを待っている人の数を示します。ホイールに乗るには、各顧客が「ボード」の金額を支払う必要があり、その金額は、ホイールを反時計回りに1回転させるためのものです。キャビンに空席がある場合、列に並んで待っている人は待つべきではありません。したがって、データを前提として、利益を最大化するために必要なローテーションの最小量を見つける必要があります。

したがって、入力がcust =[6,4]、board =6、run =4の場合、出力は3

最初は6人が並んで待っています。したがって、最初は4人が最初のキャビンに入り、残りは次のキャビンを待ちます。

ホイールが回転し、2番目のキャビンが到着します。その間、さらに4人が列に並びます。したがって、待機している次の4人は次のキャビンに入ります。

ホイールが再び回転し、残りの3人の顧客が次のキャビンに入ります。

したがって、すべての顧客にサービスを提供するには、最低3回のローテーションが必要です。

これらのローテーションから達成できる最大の利益は（10 * 6）-（3 * 4）=48です。

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

• res：=-1

• mst：=0

• tmp：=0

• wt：=0

• custの各インデックスidxと値valについて、実行します

  • wt：=wt​​ + val

  • chg：=最小（4、wt）

  • wt：=wt​​ --chg

  • tmp：=tmp +chg*ボード-実行

  • mst

    • res：=idx + 1

    • mst：=tmp

• x：=wt​​ / 4

• y：=wt​​ mod 4

• 4 *ボード>が実行された場合、

  • res：=res + x

• y *ボード>実行する場合、

  • res：=res + 1

• 解像度を返す

例

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

def solve(cust, board, run):
   res = -1
   mst = 0
   tmp = 0
   wt = 0
   for idx, val in enumerate(cust):
      wt += val
      chg = min(4, wt)
      wt -= chg
      tmp += chg * board - run
      if mst < tmp:
         res, mst = idx+1, tmp
   x, y = divmod(wt, 4)
   if 4 * board > run:
      res += x
   if y * board > run:
      res += 1
   return res

print(solve([6,4], 6, 4))

入力

[6,4], 6, 4

出力

3