Pythonで価値の低い色のボールを販売して最大の利益を見つけるプログラム

Inventoryという配列があるとします。inventory[i]は、最初に持っていたi番目の色のボールの数を表します。また、注文と呼ばれる値があります。これは、顧客が必要とするボールの総数を表します。ボールは任意の順序で販売できます。私たちの在庫にはさまざまな色のボールがあり、顧客は任意の色のボールを望んでいます。現在、ボールの価値は本質的に特別です。各色のボールの値は、在庫にあるその色のボールの数です。したがって、現在6つの青いボールがある場合、顧客は最初の青いボールに6を支払うことになります。その場合、青いボールは5つしか残っていないので、次の青いボールは5と評価されます。色付きのボールを注文した後に取得できる最大合計値を見つける必要があります。答えが大きすぎる場合は、10 ^ 9+7を法として返します。

したがって、入力が在庫=[5,7]、注文=6の場合、最初の色のボールを価格（5,4）で2回、2番目の色のボールを4回（7）販売できるため、出力は31になります。 、6,5,4）、つまり総利益5 + 4 + 7 + 6 + 5 + 4 =31

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

• 低：=0、高：=10000000

• 低<高、実行

  • mid：=（低+高）/2の商

  • s：=0

  • インベントリ内の各iについて、実行します

    • i> midの場合、

      • s：=s + i --mid

  • s>注文の場合、

    • 低：=中+ 1

  • それ以外の場合

    • 高：=中

• mid：=（低+高）/2の商

• ans：=0

• インベントリ内の各iについて、実行します

  • i> midの場合、

    • ans：=ans +（i *（i + 1）/ 2）の商-（mid *（mid + 1）/ 2）の商

    • 注文：=注文-i-mid

• ans：=ans+注文*mid

• ans mod（10 ^ 9 + 7）を返す

例

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

def solve(inventory, orders):
   low = 0
   high = 10000000

   while low < high:
      mid = (low+high)//2

      s = 0
      for i in inventory:
         if i > mid:
            s += i-mid

      if s > orders:
         low = mid+1
      else:
         high = mid


   mid = (low+high)//2

   ans = 0
   for i in inventory:
      if i > mid:
         ans += i*(i+1)//2 - mid*(mid+1)//2
         orders -= i-mid

   ans += orders*mid
   return ans % (10**9 + 7)

inventory = [5,7]
orders = 6
print(solve(inventory, orders))

入力

[6,8,7,11,5,9], [0,0,2], [2,3,5]

出力

31