销售价值减少的颜色球

标签: 贪心 数组 数学 二分查找 排序 堆（优先队列）

难度: Medium

你有一些球的库存 inventory ，里面包含着不同颜色的球。一个顾客想要 任意颜色 总数为 orders 的球。

这位顾客有一种特殊的方式衡量球的价值：每个球的价值是目前剩下的 同色球 的数目。比方说还剩下 6 个黄球，那么顾客买第一个黄球的时候该黄球的价值为 6 。这笔交易以后，只剩下 5 个黄球了，所以下一个黄球的价值为 5 （也就是球的价值随着顾客购买同色球是递减的）

给你整数数组 inventory ，其中 inventory[i] 表示第 i 种颜色球一开始的数目。同时给你整数 orders ，表示顾客总共想买的球数目。你可以按照 任意顺序 卖球。

请你返回卖了 orders 个球以后 最大 总价值之和。由于答案可能会很大，请你返回答案对 109 + 7 取余数 的结果。

 

示例 1：

输入：inventory = [2,5], orders = 4
输出：14
解释：卖 1 个第一种颜色的球（价值为 2 )，卖 3 个第二种颜色的球（价值为 5 + 4 + 3）。
最大总和为 2 + 5 + 4 + 3 = 14 。

示例 2：

输入：inventory = [3,5], orders = 6
输出：19
解释：卖 2 个第一种颜色的球（价值为 3 + 2），卖 4 个第二种颜色的球（价值为 5 + 4 + 3 + 2）。
最大总和为 3 + 2 + 5 + 4 + 3 + 2 = 19 。

示例 3：

输入：inventory = [2,8,4,10,6], orders = 20
输出：110

示例 4：

输入：inventory = [1000000000], orders = 1000000000
输出：21
解释：卖 1000000000 次第一种颜色的球，总价值为 500000000500000000 。 500000000500000000 对 109 + 7 取余为 21 。

 

提示：

  • 1 <= inventory.length <= 105
  • 1 <= inventory[i] <= 109
  • 1 <= orders <= min(sum(inventory[i]), 109)

Submission

运行时间: 104 ms

内存: 27.1 MB

MOD = 10 ** 9 + 7

class Solution:
    def maxProfit(self, inventory: List[int], orders: int) -> int:
        def total(x, y):
            return (y + x) * (y - x + 1) >> 1

        inventory.sort(reverse=True)
        ans = 0
        i = 0
        n = len(inventory)
        while orders:
            while i + 1 < n and inventory[i + 1] == inventory[i]:
                i += 1
            diff = inventory[i] - (inventory[i + 1] if i + 1 < n else 0)
            balls = (i + 1) * diff
            if balls >= orders:
                level, rest = divmod(orders, i + 1)
                bottom = inventory[i] - level
                ans += total(bottom + 1, inventory[i]) * (i + 1) + rest * bottom
                orders = 0
            else:
                ans += total(inventory[i] - diff + 1, inventory[i]) * (i + 1)
                orders -= balls
            ans %= MOD
            i += 1
        return ans

Explain

这个题解使用了贪心算法的思路来最大化球的总价值。首先，将库存数组降序排序，这样可以确保我们总是先卖出当前价值最高的球。解决方案中的关键步骤涉及处理每种颜色球的不同层级，从当前最高数量逐步向下销售。每次迭代中，我们计算可以从当前最高数量减至下一个较低数量的球总数，并决定是否可以基于剩余订单数量完成此批次的销售。如果可以，就计算这部分的总价值并结束循环；如果不行，计算所有可以卖出的球的价值，然后更新剩余订单数量，继续处理下一批。我们使用一个辅助函数total来计算从x到y的所有整数的和，以便快速计算某一层级的球的总价值。

时间复杂度: O(n log n)

空间复杂度: O(log n)

MOD = 10 ** 9 + 7

class Solution:
    def maxProfit(self, inventory: List[int], orders: int) -> int:
        def total(x, y):
            # 计算从x到y连续整数的和
            return (y + x) * (y - x + 1) >> 1

        # 降序排序库存数组
        inventory.sort(reverse=True)
        ans = 0
        i = 0
        n = len(inventory)
        while orders:
            # 统计当前层级球的数量
            while i + 1 < n and inventory[i + 1] == inventory[i]:
                i += 1
            diff = inventory[i] - (inventory[i + 1] if i + 1 < n else 0)
            balls = (i + 1) * diff
            if balls >= orders:
                level, rest = divmod(orders, i + 1)
                bottom = inventory[i] - level
                ans += total(bottom + 1, inventory[i]) * (i + 1) + rest * bottom
                orders = 0
            else:
                ans += total(inventory[i] - diff + 1, inventory[i]) * (i + 1)
                orders -= balls
            ans %= MOD
            i += 1
        return ans

Explore

在题解中，库存数组被降序排序主要是为了确保每次销售都能从价值最高的球开始，从而最大化总收益。降序排序后，数组的第一个元素是库存中数量最多的，也即是单个球价值最高的。这样，我们可以优先销售这些球，直到它们的数量降至下一个层级，即第二多的数量。这种方法确保每一步操作都是在当前情况下可能的最佳选择，符合贪心算法的策略。

辅助函数`total(x, y)`用于计算从整数x到整数y的所有连续整数的和。该函数的计算方法基于等差数列求和公式，即`(y + x) * (y - x + 1) / 2`。这个公式利用了等差数列的首项加末项乘以项数除以2的特点来快速计算和。在题解中，这个函数被用来计算每一层级销售球的总价值。例如，如果从某一数量级的球需要销售到下一个较低的数量级，函数可以快速得出这些球的总价值，从而有效地计算出在满足订单的情况下可以获得的最大收益。

在题解中，‘层级’是指具有相同数量的球的一组或多组颜色。这些层级是通过降序排序后相邻元素之间的数量差异确定的。例如，如果有球的数量排序后为[5,5,3,1]，则存在三个层级：数量为5的层级（包含两个颜色），数量为3的层级（包含一个颜色），和数量为1的层级（包含一个颜色）。在算法中，每次迭代处理最高层级的球，计算可以从这个层级销售的球的总数和价值，然后移动到下一个层级。这样的处理确保我们能够最大化每次销售的利润，因为总是优先销售数量最多且价值最高的球。