使用Python找到售出不断减值的彩球的最大利润

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

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

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

low := 0，high := 10000000
当low < high时执行以下操作
- mid := 底数除以 (low + high)/2
- s := 0
- for each i in inventory do
  - 如果 i > mid，则
  - s := s + i – mid
- 如果 s > orders，则
  - low := mid + 1
- 否则
  - high := mid
mid := 底数除以 (low + high)/2
ans := 0
for each i in inventory do
- 如果 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
    returnans % (10 ** 9 + 7)

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