销售价值减少的颜色球
难度:
标签:
题目描述
你有一些球的库存 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)
代码结果
运行时间: 104 ms, 内存: 27.1 MB
/*
* Solution idea using Java Streams:
* 1. Sort the inventory in descending order using streams.
* 2. Utilize a loop to continuously sell balls from the most valuable to least.
* 3. Calculate the maximum profit using streams for sorting and reduction operations.
* 4. Ensure handling of large numbers with modulo operation.
*/
import java.util.Arrays;
import java.util.Collections;
public class BallSaleStream {
public int maxProfit(int[] inventory, int orders) {
int MOD = 1000000007;
Integer[] sortedInventory = Arrays.stream(inventory).boxed().toArray(Integer[]::new);
Arrays.sort(sortedInventory, Collections.reverseOrder());
long profit = 0;
int i = 0;
while (orders > 0 && i < sortedInventory.length) {
int currentMax = sortedInventory[i];
int nextMax = (i + 1 < sortedInventory.length) ? sortedInventory[i + 1] : 0;
int sell = Math.min(orders, (currentMax - nextMax) * (i + 1));
int fullRound = sell / (i + 1);
profit = (profit + (long) fullRound * (2 * currentMax - fullRound + 1) / 2 * (i + 1)) % MOD;
int remaining = sell % (i + 1);
profit = (profit + (long) remaining * (currentMax - fullRound)) % MOD;
orders -= sell;
i++;
}
return (int) profit;
}
}解释
方法:
这个题解使用了贪心算法的思路来最大化球的总价值。首先，将库存数组降序排序，这样可以确保我们总是先卖出当前价值最高的球。解决方案中的关键步骤涉及处理每种颜色球的不同层级，从当前最高数量逐步向下销售。每次迭代中，我们计算可以从当前最高数量减至下一个较低数量的球总数，并决定是否可以基于剩余订单数量完成此批次的销售。如果可以，就计算这部分的总价值并结束循环；如果不行，计算所有可以卖出的球的价值，然后更新剩余订单数量，继续处理下一批。我们使用一个辅助函数total来计算从x到y的所有整数的和，以便快速计算某一层级的球的总价值。
时间复杂度:
O(n log n)
空间复杂度:
O(log n)
代码细节讲解
🦆
在题解中，为什么选择将库存数组进行降序排序？这样的排序对解决问题有哪些具体帮助？
▷🦆
题解提到了使用一个辅助函数`total`来计算从x到y的连续整数和，能否详细解释这个函数的计算方法及其在此问题中的作用？
▷🦆
解决方案中提到了处理每种颜色球的不同层级，如何确定这些层级，并且它们在算法中扮演什么角色？
▷