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:

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的球。

代码参考自花花。

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