用 Python 编写程序，通过出售价值递减的彩球来获取最大利润

pythonserver side programmingprogramming更新于 2025/11/30 11:56:17

假设我们有一个名为 inventory 的数组，其中 inventory[i] 表示我们最初拥有的第 i 种颜色的球的数量。我们还有一个名为 orders 的值，它表示客户想要的球的总数。我们可以按任何顺序出售球。我们的库存中有不同颜色的球，客户想要任何颜色的球。现在球的价值本质上是特殊的。每个彩色球的价值是我们库存中该颜色球的数量。因此，如果我们目前有 6 个蓝球，客户将为第一个蓝球支付 6 美元。然后只剩下 5 个蓝球，所以下一个蓝球的价值为 5 美元。我们必须找到在出售 order 个彩色球后可以获得的最大总价值。如果答案太大，则返回其模 10^9 + 7。

因此，如果输入为 inventory = [5,7], orders = 6，则输出将为 31，因为我们可以以价格 (5,4) 卖出第一个彩球两次，以价格 (7,6,5,4) 卖出第二个彩球四次，因此总利润 5+4+7+6+5+4 = 31

为了解决这个问题，我们将遵循以下步骤 −

low := 0, high := 10000000
while low <高，执行
- 中 := (低 + 高)/2 的商
- s := 0
- 对于库存中的每个 i，执行
  - 如果 i > 中，则
    - s := s + i - 中
- 如果 s >订单，则
  - low := mid + 1
- 否则，
  - high := mid
mid := (low + high)/2 的商
ans := 0
对于库存中的每个 i，执行
- 如果 i > mid，然后
  - ans := ans + (i*(i+1)/2) 的商 - (mid*(mid+1)/2) 的商
  - orders := orders - i-mid
ans := ans + orders * 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))