> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/greedy/1648.-sell-diminishing-valued-colored-balls.md).

# 1648. Sell Diminishing-Valued Colored Balls

https\://leetcode.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 `ith` 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**9 + 7`.

**Example 1:**![](https://assets.leetcode.com/uploads/2020/11/05/jj.gif)

```
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 109 + 7 = 21.
```

**Constraints:**

* `1 <= inventory.length <= 10**5`
* `1 <= inventory[i] <= 10**9`
* `1 <= orders <= min(sum(inventory[i]), 10**9)`

一堆有颜色的球，每个球得分为同颜色球当前的频次，问取orders次能得到最高分。题目要求暗示时间复杂度O(N)或O(NlgN)，与inventory取值无甚关系。为了让分更高，一定会从当前频率最高的球开始拿，直到频次降到次高，贪心。因此按频次从大到小排序，一次性将最高分球的频次全部取到次高，得分为等差数列=(当前最高频次cur + 次高值nxt) \* 项数(cur - nxt) \*最高频次出现次数i。当orders不足即 < i \* (cur - nxt)时，能取t = orders // i 所有最高频次球，剩下orders % i次取取完整数次后最高频次nxt\_p的球。

代码参考自花花。

```python
class Solution:
    def maxProfit(self, inventory: List[int], orders: int) -> int:
        MOD = 10 ** 9 + 7
        inventory.sort(reverse=True)
        res, cur, i, N = 0, inventory[0], 0, len(inventory)  
        while orders:
            while i < N and inventory[i] == cur: i += 1
            nxt = 0 if i == N else inventory[i]
            cnt = min(orders, i * (cur - nxt))
            t = cur - nxt
            r = 0
            if orders < i * (cur - nxt):
                t = orders // i
                r = orders % i
            nxt_p = cur - t
            res = (res + (cur + nxt_p + 1) * t // 2 * i + nxt_p * r) % MOD
            orders -= cnt
            cur = nxt
        return res
        
```