列表

详情

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

你有一些球的库存 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 。

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: int maxProfit(vector<int>& inventory, int orders) { } };

golang 解法, 执行用时: 104 ms, 内存消耗: 8.9 MB, 提交时间: 2023-10-08 23:18:41 

func maxProfit(inventory []int, orders int) int {
    MOD := 1000000007

    l, r := 0, int(1e9)

    getCount := func(mid int) int {
        count := 0
        for i := range inventory {
            if inventory[i] > mid {
                count += inventory[i]-mid
            }
        }
        return count
    }

    sum := func(i, j int) int {
        // n*a1 + n*(n-1)/2
        a1, n := i+1, j-i
        return n*a1 + n*(n-1)/2
    }

    for l < r {
        mid := (l+r) >> 1
        count := getCount(mid)
        if count < orders {
            r = mid
        } else {
            l = mid + 1
        }
    }

    res := (orders - getCount(l)) * l

    for i := range inventory {
        if inventory[i] > l {
            res += (sum(l, inventory[i]))%MOD

        }
    }

    return res % MOD
}

golang 解法, 执行用时: 132 ms, 内存消耗: 9 MB, 提交时间: 2023-10-08 23:18:27 

func maxProfit(inventory []int, orders int) int {
      ans:=0
	  mod:=1000000007
      inventory = append(inventory,0)
      sort.Ints(inventory)
      n:=len(inventory)
      for i:=n-1;i>0;i--{
      	  if orders<=0{
      	  	break
		  }
      	  if (n-i)*(inventory[i]-inventory[i-1])<=orders{
      	  	 sum:=(inventory[i]+inventory[i-1]+1)*(inventory[i]-inventory[i-1])/2*(n-i)
      	  	 ans=(ans+sum)%mod
      	  	 orders-=(n-i)*(inventory[i]-inventory[i-1])
		  }else {
		  	 n1:=orders/(n-i)
		  	 n2:=orders%(n-i)
		  	 x:=inventory[i]-n1+1
		  	 sum:=(inventory[i]+x)*n1/2*(n-i)+n2*(x-1)
		  	 ans=(ans+sum)%mod
		  	 orders=0
		  }
	  }
	  return ans
}

java 解法, 执行用时: 22 ms, 内存消耗: 52.7 MB, 提交时间: 2023-10-08 23:17:27 

/**
 * 再碰见(int) 1e9 + 7; 别用int
 * 按照每组最多剩下多少个球，二分。
 * 平均最多剩下多少，能保证卖够orders数量。平均不是真的平均..是说所有大于这个数的，
 * 卖剩下这个数，够orders。如果卖剩下的数量，比这个多的话，卖出去的不够orders。
 * 这数 + 1 价值的球，未必需要都卖出去。
 * ((orders - sum) * cut)是真正价值严格等于 cut + 1卖出去的数量。
 */
class Solution {
	int mod = (int) 1e9 + 7;

	public int maxProfit(int[] inventory, int orders) {
		int max = 0;
		for (int i = 0; i < inventory.length; i++) {
			max = Math.max(max, inventory[i]);
		}
		long l = 0, r = max;
		long cut = 0;
		while (l <= r) {
			long mid = l + ((r - l) >> 1);
			long sum = 0;
			for (long num : inventory) {
				if (num > mid) {
					long size = num - mid;
					sum += size;
				}
			}
			if (sum >= orders) {
				cut = mid;
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		long sum = 0;
		cut += 1;
		long ans = 0;
		for (long num : inventory) {
			if (num > cut) {
				long size = num - cut;
				sum += size;
				ans += ((num + cut + 1) * size / 2) % mod;
				ans %= mod;
			}
		}
		ans += ((orders - sum) * cut) % mod;
		ans %= mod;
		return (int) ans;
	}
}

python3 解法, 执行用时: 404 ms, 内存消耗: 27.6 MB, 提交时间: 2023-10-08 23:10:27 

class Solution:
    # 二分 + 贪心
    def maxProfit(self, inventory: List[int], orders: int) -> int:
        mod = 10**9 + 7
        
        # 二分查找 T 值
        l, r, T = 0, max(inventory), -1
        while l <= r:
            mid = (l + r) // 2
            total = sum(ai - mid for ai in inventory if ai >= mid)
            if total <= orders:
                T = mid
                r = mid - 1
            else:
                l = mid + 1

        range_sum = lambda x, y: (x + y) * (y - x + 1) // 2
        
        rest = orders - sum(ai - T for ai in inventory if ai >= T)
        ans = 0
        for ai in inventory:
            if ai >= T:
                if rest > 0:
                    ans += range_sum(T, ai)
                    rest -= 1
                else:
                    ans += range_sum(T + 1, ai)
                    
        return ans % mod

cpp 解法, 执行用时: 104 ms, 内存消耗: 63.6 MB, 提交时间: 2023-10-08 23:10:03 

class Solution {
private:
    using LL = long long;
    
    static constexpr int mod = 1000000007;
    
    static constexpr LL rangeSum(int x, int y) {
        return static_cast<LL>(x + y) * (y - x + 1) / 2;
    }

public:
    int maxProfit(vector<int>& inventory, int orders) {
        int l = 0;
        int r = *max_element(inventory.begin(), inventory.end());
        int T = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            LL total = accumulate(inventory.begin(), inventory.end(), 0LL, [&](LL acc, int ai) {
                return acc + max(ai - mid, 0);
            });
            if (total <= orders) {
                T = mid;
                r = mid - 1;
            }
            else {
                l = mid + 1;
            }
        }
        int rest = orders - accumulate(inventory.begin(), inventory.end(), 0, [&](int acc, int ai) {
            return acc + max(ai - T, 0);
        });
        LL ans = 0;
        for (int ai: inventory) {
            if (ai >= T) {
                if (rest > 0) {
                    ans += rangeSum(T, ai);
                    --rest;
                }
                else {
                    ans += rangeSum(T + 1, ai);
                }
            }
        }
        return ans % mod;
    }
};

cpp 解法, 执行用时: 112 ms, 内存消耗: 63.6 MB, 提交时间: 2023-10-08 23:09:21 

class Solution {
public:
    // 模拟
    int maxProfit1(vector<int>& nums, int orders) {
        sort(nums.begin(), nums.end(), greater<int>());
        long res = 0, mod = 1e9 + 7;
        int j = 0;
        while(orders > 0) {
            while(j < nums.size() && nums[j] >= nums[0]) {
                ++j;
            }
            int next = 0;
            if(j < nums.size()) {
                next = nums[j];
            }
            long bucks = j, delta = nums[0] - next;
            long rem = bucks * delta;
            if(rem > orders) {
                long dec = orders / bucks;
                long a1 = nums[0] - dec + 1, an = nums[0];
                res += (((a1 + an) * dec) / 2) * bucks;
                res += (nums[0] - dec) * (orders % bucks);
            } else {
                long a1 = next + 1, an = nums[0];
                res += (((a1 + an) * delta) / 2) * bucks;
                nums[0] = next;
            }
            orders -= rem;
            res %= mod;
        }
        return res;
    }


    bool ck(vector<int>& nums, int x, int orders) {
        int sum = 0;
        for(int i : nums) {
            sum += max(i - x, 0);
            if(sum > orders) {
                return true;
            }
        }
        return false;
    }
    
    // 二分
    int maxProfit(vector<int>& nums, int orders) {
        int l = 0, r = 1e9;
        while(l < r) {
            int mid = (l + r) >> 1;
            if(ck(nums, mid, orders)) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        long res = 0, mod = 1e9 + 7;
        for(int i : nums) {
            if(i > l) {
                res += ((long)(i + l + 1) * (long)(i - l)) >> 1;
                res %= mod;
                orders -= i - l;
            }
        }
        res += (long)l * (long)orders;
        res %= mod;
        return res;
    }
};

上一题

© 2024 leetcode.cn