1648. 销售价值减少的颜色球 #

问题描述#

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

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

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

请你返回卖了 orders 个球以后最大总价值之和。由于答案可能会很大，请你返回答案对 10⁹ + 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 对 10⁹+ 7 取余为 21 。
提示：

1 <= inventory.length <= 10⁵

1 <= inventory[i] <= 10⁹

1 <= orders <= min(sum(inventory[i]), 10⁹)

解题思路#

球的总价值为:

\[ \sum_{i=1}^{\text{len}(\text{inventory})}\sum_{j=1}^{\text{inventory}[i]}(j) \]

问题简单来说就是要从里面取最大的 orders 项之和。

如对于示例：

1 2	`inventory = [2,5] orders = 4`

总价值为 \((5+4+3+2+1)+(2+1)\)，最大的前 4 项之和为 \(5+4+3+2=14\)。

但是实际问题的规模可能很大（最多可能有 \(10^9*10^5\) 个数），对这些数排序后取前 orders 项之和是不可能的。

其实我们可以不用一个一个数取，如对于开始的最大值 5，我们至少可以连续取 5、4、3，因为到 3 之前，它们一直都是最大值，即我们可以一直取到次小值为止。

如果有相同的最大值 upper，就乘以相同最大值的个数 width 即可，即在到达次小值 lower - 1 时，我们至少可以取 (upper - lower) * width 个数，这些数的总价值为 (upper + lower) * (upper - lower + 1) // 2 * width。最后的结果对 10**9+7 取余。

        +---------+
upper   |*********|
  ^     |*********|
  |     |*********|
  V     |*********|
lower   |*********|
        +---------+
           width

对于示例：

1 2	`inventory = [2,8,4,10,6] orders = 20`

10  * 
 9  * 
 8  * * 
 7  * * 
 6  * * * 
 5  * * * 
 4  * * * *  
 3  * * * * 
 2  * * * * * 
 1  * * * * *

每次取数的顺序为从左到右、从上到下，一直到取了 orders 个数。

value  +-+
   10  |*|
    9  |*|
       +-+
       +---+
    8  |* *|
    7  |* *|
       +---+
       +-----+
    6  |* * *|
    5  |* * *|
       +-----+
       +-------+
    4  |* * * *| 
    3  |* * * *|
       +-------+
       +---------+
    2  |* * * * *|
    1  |* * * * *|
       +---------+

class Solution:
    def maxProfit(self, inventory: List[int], orders: int) -> int:
        inventory.sort(reverse=True)
        inventory.append(0)

        ans = 0
        MOD = 10 ** 9 + 7
        upper = inventory[0]
        for width, value in enumerate(inventory[1:], 1):
            if orders == 0:
                break
            if value == upper: # 目前有多少个相同的最大值
                continue

            x, y = divmod(orders, width)
            if x >= upper - value: # 剩下的 orders 数量能够取完这一批
                lower = value + 1
                values = (upper + lower) * (upper - lower + 1) // 2 * width
                ans = (ans + values) % MOD
                orders -= width * (upper - lower + 1)
            else: # 不够取
                lower = upper - x + 1
                values = (upper + lower) * (upper - lower + 1) // 2 * width + y * (
                    lower - 1
                )
                ans = (ans + values) % MOD
                break
            upper = value
        return ans

1648. 销售价值减少的颜色球#

问题描述#

解题思路#

1648. 销售价值减少的颜色球 #