Calculate Revenue from Highest-Inventory VM Sales

A provider sells units from several VM inventory types. The price of one unit equals that type's current remaining inventory immediately before the sale. Each customer buys one unit from a type with the greatest current inventory, then that type's inventory decreases by one.

Function Signature

vm_revenue(inventory: list[int], customers: int) -> int

Output

Return total revenue after serving exactly customers customers. Any type tied for greatest inventory may be chosen; the total revenue is unchanged by that tie choice. Types with zero inventory cannot be sold.

Constraints

• 1 <= len(inventory) <= 200000.
• 0 <= inventory[i] <= 1000000000.
• 0 <= customers <= 200000.
• customers <= sum(inventory).
• Use an integer type large enough for the total revenue, which may exceed a signed 32-bit integer.
• Do not mutate the input array.

Examples

Input: inventory = [1,2,4], customers = 4

Output: 11

The four sale prices are 4, 3, 2, and 2.

Input: inventory = [2,2], customers = 3

Output: 5

Input: inventory = [0,3], customers = 0

Output: 0

Total Revenue from Selling the Largest Remaining VM Inventory

A provider sells virtual-machine units from several inventory types. inventory[i] is the number of units currently available for type i.

Customers are served one at a time. Each customer buys exactly one unit from a type that currently has the greatest remaining inventory. The price of that unit equals that type's remaining inventory immediately before the sale; afterwards, that type's inventory decreases by one. A type whose remaining inventory is zero cannot be sold.

Given inventory and an integer customers, return the total revenue collected after serving exactly customers customers.

If several types are tied for the greatest remaining inventory, any one of them may be chosen. The total revenue is unchanged by that tie choice, so the returned value is unique. Do not mutate the input array.

The total revenue may exceed a signed 32-bit integer, so use a 64-bit integer type (long in Java, long long in C++).

Example 1:

Input: inventory = [1, 2, 4], customers = 4
Output: 11

Explanation: The four sale prices are 4, 3, 2, and 2. The type that started at 4 is sold down to 2, at which point it ties with the type that started at 2, and the last two customers each pay 2.

Example 2:

Input: inventory = [2, 2], customers = 3
Output: 5

Explanation: Both types start tied at 2, so the prices are 2, 2, and 1 for a total of 5, whichever tied type each customer picks.

Example 3:

Input: inventory = [0, 3], customers = 0
Output: 0

Explanation: No customer is served, so no revenue is collected.

Hints

1. Because the price is always the current greatest remaining inventory, the answer does not depend on which tied type a customer picks - only on the multiset of remaining inventories after each sale.
2. customers can be far smaller than sum(inventory), but it can also be much larger than the number of distinct inventory values. Ask how many types share the greatest value at any moment, and how that count changes as the greatest value falls.
3. The money collected while one type is sold from a units down to b units is a sum of consecutive integers; a closed form for that sum avoids charging customers one at a time, but remember the budget can run out midway.