你有一些球的库存 inventory ，里面包含着不同颜色的球。一个顾客想要 任意颜色 总数为 orders 的球。
这位顾客有一种特殊的方式衡量球的价值：每个球的价值是目前剩下的 同色球 的数目。比方说还剩下 6 个黄球，那么顾客买第一个黄球的时候该黄球的价值为 6 。这笔交易以后，只剩下 5 个黄球了，所以下一个黄球的价值为 5 （也就是球的价值随着顾客购买同色球是递减的）
给你整数数组 inventory ，其中 inventory[i] 表示第 i 种颜色球一开始的数目。同时给你整数 orders ，表示顾客总共想买的球数目。你可以按照 任意顺序 卖球。
请你返回卖了 orders 个球以后 最大 总价值之和。由于答案可能会很大，请你返回答案对 109 + 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 对 109 + 7 取余为 21 。
提示：
1 <= inventory.length <= 1051 <= inventory[i] <= 1091 <= orders <= min(sum(inventory[i]), 109)
方法一：贪心 + 优化模拟
要使得总价值最大，我们可以贪心地每次卖出数量最多的一种颜色的球。由于 orders 值域较大，如果直接简单地模拟，会超时。因此，我们需要优化模拟的过程。
实际上，我们不需要一次次进行模拟，我们可以跟踪数量最多的同色球的种类数 cnt，每一次可以卖出一批球，从而达到加速模拟的目的。
时间复杂度 inventory 的长度。
class Solution:
def maxProfit(self, inventory: List[int], orders: int) -> int:
inventory.sort(reverse=True)
mod = 10**9 + 7
ans = i = 0
n = len(inventory)
while orders > 0:
while i < n and inventory[i] >= inventory[0]:
i += 1
nxt = 0
if i < n:
nxt = inventory[i]
cnt = i
x = inventory[0] - nxt
tot = cnt * x
if tot > orders:
decr = orders // cnt
a1, an = inventory[0] - decr + 1, inventory[0]
ans += (a1 + an) * decr // 2 * cnt
ans += (inventory[0] - decr) * (orders % cnt)
else:
a1, an = nxt + 1, inventory[0]
ans += (a1 + an) * x // 2 * cnt
inventory[0] = nxt
orders -= tot
ans %= mod
return ansclass Solution {
private static final int MOD = (int) 1e9 + 7;
public int maxProfit(int[] inventory, int orders) {
Arrays.sort(inventory);
int n = inventory.length;
for (int i = 0, j = n - 1; i < j; ++i, --j) {
int t = inventory[i];
inventory[i] = inventory[j];
inventory[j] = t;
}
long ans = 0;
int i = 0;
while (orders > 0) {
while (i < n && inventory[i] >= inventory[0]) {
++i;
}
int nxt = i < n ? inventory[i] : 0;
int cnt = i;
long x = inventory[0] - nxt;
long tot = cnt * x;
if (tot > orders) {
int decr = orders / cnt;
long a1 = inventory[0] - decr + 1, an = inventory[0];
ans += (a1 + an) * decr / 2 * cnt;
ans += (a1 - 1) * (orders % cnt);
} else {
long a1 = nxt + 1, an = inventory[0];
ans += (a1 + an) * x / 2 * cnt;
inventory[0] = nxt;
}
orders -= tot;
ans %= MOD;
}
return (int) ans;
}
}class Solution {
public:
int maxProfit(vector<int>& inventory, int orders) {
long ans = 0, mod = 1e9 + 7;
int i = 0, n = inventory.size();
sort(inventory.rbegin(), inventory.rend());
while (orders > 0) {
while (i < n && inventory[i] >= inventory[0]) {
++i;
}
int nxt = i < n ? inventory[i] : 0;
int cnt = i;
long x = inventory[0] - nxt;
long tot = cnt * x;
if (tot > orders) {
int decr = orders / cnt;
long a1 = inventory[0] - decr + 1, an = inventory[0];
ans += (a1 + an) * decr / 2 * cnt;
ans += (a1 - 1) * (orders % cnt);
} else {
long a1 = nxt + 1, an = inventory[0];
ans += (a1 + an) * x / 2 * cnt;
inventory[0] = nxt;
}
orders -= tot;
ans %= mod;
}
return ans;
}
};func maxProfit(inventory []int, orders int) int {
var mod int = 1e9 + 7
i, n, ans := 0, len(inventory), 0
sort.Ints(inventory)
for i, j := 0, n-1; i < j; i, j = i+1, j-1 {
inventory[i], inventory[j] = inventory[j], inventory[i]
}
for orders > 0 {
for i < n && inventory[i] >= inventory[0] {
i++
}
nxt := 0
if i < n {
nxt = inventory[i]
}
cnt := i
x := inventory[0] - nxt
tot := cnt * x
if tot > orders {
decr := orders / cnt
a1, an := inventory[0]-decr+1, inventory[0]
ans += (a1 + an) * decr / 2 * cnt
ans += (a1 - 1) * (orders % cnt)
} else {
a1, an := nxt+1, inventory[0]
ans += (a1 + an) * x / 2 * cnt
inventory[0] = nxt
}
orders -= tot
ans %= mod
}
return ans
}