Question

1648. 销售价值减少的颜色球

English Version

题目描述

你有一些球的库存 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 <= 105
• 1 <= inventory[i] <= 109
• 1 <= orders <= min(sum(inventory[i]), 109)

解法

方法一：贪心 + 优化模拟

要使得总价值最大，我们可以贪心地每次卖出数量最多的一种颜色的球。由于 orders 值域较大，如果直接简单地模拟，会超时。因此，我们需要优化模拟的过程。

实际上，我们不需要一次次进行模拟，我们可以跟踪数量最多的同色球的种类数 cnt，每一次可以卖出一批球，从而达到加速模拟的目的。

时间复杂度 $O(n\log n)$，空间复杂度 $O(1)$。其中 $n$ 为数组 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 ans

class 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
}