Skip to content

Latest commit

 

History

History
233 lines (193 loc) · 7.4 KB

File metadata and controls

233 lines (193 loc) · 7.4 KB

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 的长度。

Python3

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

Java

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

C++

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

Go

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
}

...