1648. 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 `109 + 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 = , 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 <= 105`
• `1 <= inventory[i] <= 109`
• `1 <= orders <= min(sum(inventory[i]), 109)`

1648. Sell Diminishing-Valued Colored Balls
``````struct Solution;

const MOD: i64 = 1_000_000_007;

impl Solution {
fn max_profit(mut inventory: Vec<i32>, mut orders: i32) -> i32 {
let n = inventory.len();
inventory.sort_unstable();
let mut res: i64 = 0;
for i in (0..n).rev() {
let diff = if i > 0 {
inventory[i] - inventory[i - 1]
} else {
inventory[i]
};
let w = (n - i) as i32;
if orders >= diff * w {
res += (inventory[i] - diff + 1 + inventory[i]) as i64 * diff as i64 / 2 * w as i64;
res %= MOD;
orders -= diff * w;
} else {
let diff = orders / w;
res += (inventory[i] - diff + 1 + inventory[i]) as i64 * diff as i64 / 2 * w as i64;
res %= MOD;
orders -= diff * w;
let h = inventory[i] - diff;
while orders > 0 {
res += h as i64;
res %= MOD;
orders -= 1;
}
break;
}
}
res as i32
}
}

#[test]
fn test() {
let inventory = vec![2, 5];
let orders = 4;
let res = 14;
assert_eq!(Solution::max_profit(inventory, orders), res);
let inventory = vec![3, 5];
let orders = 6;
let res = 19;
assert_eq!(Solution::max_profit(inventory, orders), res);
let inventory = vec![2, 8, 4, 10, 6];
let orders = 20;
let res = 110;
assert_eq!(Solution::max_profit(inventory, orders), res);
let inventory = vec![2, 8, 4, 10, 6];
let orders = 20;
let res = 110;
assert_eq!(Solution::max_profit(inventory, orders), res);
let inventory = vec!;
let orders = 1000000000;
let res = 21;
assert_eq!(Solution::max_profit(inventory, orders), res);
}
``````