1648-销售价值减少的颜色球(Sell Diminishing-Valued Colored Balls)

原文链接: https://leetcode-cn.com/problems/sell-diminishing-valued-colored-balls

英文原文

You have an inventory of different colored balls, and there is a customer that wants orders balls of any color.

The customer weirdly values the colored balls. Each colored ball's value is the number of balls of that color you currently have in your inventory. For example, if you own 6 yellow balls, the customer would pay 6 for the first yellow ball. After the transaction, there are only 5 yellow balls left, so the next yellow ball is then valued at 5 (i.e., the value of the balls decreases as you sell more to the customer).

You are given an integer array, inventory, where inventory[i] represents the number of balls of the i^th color that you initially own. You are also given an integer orders, which represents the total number of balls that the customer wants. You can sell the balls in any order.

Return the maximum total value that you can attain after selling orders colored balls. As the answer may be too large, return it modulo 10⁹+ 7.

Example 1:

Input: inventory = [2,5], orders = 4
Output: 14
Explanation: Sell the 1st color 1 time (2) and the 2nd color 3 times (5 + 4 + 3).
The maximum total value is 2 + 5 + 4 + 3 = 14.

Example 2:

Input: inventory = [3,5], orders = 6
Output: 19
Explanation: Sell the 1st color 2 times (3 + 2) and the 2nd color 4 times (5 + 4 + 3 + 2).
The maximum total value is 3 + 2 + 5 + 4 + 3 + 2 = 19.

Example 3:

Input: inventory = [2,8,4,10,6], orders = 20
Output: 110

Example 4:

Input: inventory = [1000000000], orders = 1000000000
Output: 21
Explanation: Sell the 1st color 1000000000 times for a total value of 500000000500000000. 500000000500000000 modulo 10⁹+ 7 = 21.

Constraints:

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

中文题目

你有一些球的库存 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⁹)

通过代码

高赞题解

方法一：贪心 + 二分查找

思路与算法

首先，贪心的思路很容易想到：我们每次会找到当前剩余最多的那一类球（如果有多个类剩余的球数相同，那么任意选择一个类即可），然后将一个这类的球卖给顾客。我们连续这样操作 $\textit{orders}$ 次，就可以卖出最大的价值。

既然我们每一次操作都要「找最大值」，那么我们可以想到使用「优先队列（大根堆）」这一数据结构，它可以使得我们：

在初始时把每一类球的数量全部放入优先队列中；
每一次操作时，取出堆顶的元素并累加入答案，再将其减去 $1$ 放回堆中。

这样做的时间复杂度为 $O(\textit{orders} \cdot \log n)$，而本题中 $\textit{orders}$ 可以到 $10^9$，会导致其超出时间限制。那么有什么可以优化的地方呢？

我们可以这样想：由于每次我们都是将当前的最大值减去 $1$，那么可以看成我们维护了一个「最大值集合」：如果其中有 $x$ 个元素，那么我们需要 $x$ 次操作把它们都减去 $1$。在这之后，可能会有不在「最大值集合」中的元素现在也变成最大值了，我们就将这些元素也加入集合中，并且继续轮流减去 $1$，直到进行了 $\textit{orders}$ 次操作。

如果把这 $\textit{orders}$ 次操作看成一个整体，那么一定存在一个「阈值」$T$（也就是最后「最大值集合」对应的那个值），使得：

初始时所有小于 $T$ 的元素都保持不变；
初始时所有大于等于 $T$ 的元素要么变成了 $T-1$（在「最大值集合」中，并且减去了 $1$），要么变成了 $T$（在最大值集合中，但是没来得及被减去 $1$）。

那么如何求出这个 $T$ 呢？对于每一个元素 $a_i$，如果它大于等于 $T$，那么它被减去 $1$ 的次数要么是 $a_i - T$，要么是 $a_i - T + 1$，所以满足题目要求的 $T$ 即为满足

$$
\sum_{a_i \geq T} (a_i - T) \leq \textit{orders} < \sum_{a_i \geq T} (a_i - T + 1)
$$

的 $T$ 值。由于随着 $T$ 的减小，$\sum_{a_i \geq T} (a_i - T)$ 是单调递增的，所以满足上述不等式要求的 $T$ 值是唯一的，并且我们可以使用二分查找的方法找出这个 $T$，即为最小的满足

$$
\sum_{a_i \geq T} (a_i - T) \leq \textit{orders}
$$

的 $T$ 值。二分查找的下界为 $0$，上界为所有 $a_i$ 中的最大值。

在求出了 $T$ 值之后，我们也可以很方便地算出答案了：令 $\textit{rest} = \textit{orders} - \sum_{a_i \geq T} (a_i - T)$，即表示有 $\textit{rest}$ 个大于等于 $T$ 的元素 $a_i$ 最后变成了 $T-1$，其余的变成了 $T$。随后我们遍历每一个元素：

如果 $a_i < T$，那么它不会有任何变化，对答案也没有贡献；
如果 $a_i \geq T$，那么根据 $\textit{rest}$ 的值考虑将 $[T, a_i]$ 或者 $[T+1, a_i]$ 计入答案。

代码

[sol1-C++]
class Solution {
private:
    using LL = long long;
    
    static constexpr int mod = 1000000007;
    
    static constexpr LL rangeSum(int x, int y) {
        return static_cast<LL>(x + y) * (y - x + 1) / 2;
    }

public:
    int maxProfit(vector<int>& inventory, int orders) {
        int l = 0;
        int r = *max_element(inventory.begin(), inventory.end());
        int T = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            LL total = accumulate(inventory.begin(), inventory.end(), 0LL, [&](LL acc, int ai) {
                return acc + max(ai - mid, 0);
            });
            if (total <= orders) {
                T = mid;
                r = mid - 1;
            }
            else {
                l = mid + 1;
            }
        }
        int rest = orders - accumulate(inventory.begin(), inventory.end(), 0, [&](int acc, int ai) {
            return acc + max(ai - T, 0);
        });
        LL ans = 0;
        for (int ai: inventory) {
            if (ai >= T) {
                if (rest > 0) {
                    ans += rangeSum(T, ai);
                    --rest;
                }
                else {
                    ans += rangeSum(T + 1, ai);
                }
            }
        }
        return ans % mod;
    }
};

[sol1-Python3]
class Solution:
    def maxProfit(self, inventory: List[int], orders: int) -> int:
        mod = 10**9 + 7
        
        # 二分查找 T 值
        l, r, T = 0, max(inventory), -1
        while l <= r:
            mid = (l + r) // 2
            total = sum(ai - mid for ai in inventory if ai >= mid)
            if total <= orders:
                T = mid
                r = mid - 1
            else:
                l = mid + 1

        range_sum = lambda x, y: (x + y) * (y - x + 1) // 2
        
        rest = orders - sum(ai - T for ai in inventory if ai >= T)
        ans = 0
        for ai in inventory:
            if ai >= T:
                if rest > 0:
                    ans += range_sum(T, ai)
                    rest -= 1
                else:
                    ans += range_sum(T + 1, ai)
                    
        return ans % mod

复杂度分析

时间复杂度：$O(n \log C)$，其中 $n$ 是数组 $\textit{inventory}$ 的长度，$C$ 是数组 $\textit{inventory}$ 中的最大值，不会超过 $10^9$。
空间复杂度：$O(1)$。

统计信息

通过次数	提交次数	AC比率
3686	13150	28.0%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途