你有一些球的库存 inventory ,里面包含着不同颜色的球。一个顾客想要 任意颜色 总数为 orders 的球。
这位顾客有一种特殊的方式衡量球的价值:每个球的价值是目前剩下的 同色球 的数目。比方说还剩下 6 个黄球,那么顾客买第一个黄球的时候该黄球的价值为 6 。这笔交易以后,只剩下 5 个黄球了,所以下一个黄球的价值为 5 (也就是球的价值随着顾客购买同色球是递减的)
给你整数数组 inventory ,其中 inventory[i] 表示第 i 种颜色球一开始的数目。同时给你整数 orders ,表示顾客总共想买的球数目。你可以按照 任意顺序 卖球。
请你返回卖了 orders 个球以后 最大 总价值之和。由于答案可能会很大,请你返回答案对 109 + 7 取余数 的结果。
逻辑看注释:
/** * @param {number[]} inventory * @param {number} orders * @return {number} */ var maxProfit = function(inventory, orders) { // 从大到小排序 inventory.sort((a, b) => b - a) // 记录数组下标 let i = 0 let res = BigInt(0) // 存储最小值 let min = 0 let flag = true while(flag) { // 如果当前数字和下一索引的数字是一样,那么往后移动,直到和下一个不等 while(inventory[i] === inventory[i + 1]) { i++ } // 计算和下一位相差的值,再乘以当前索引的长度,得到此次可以消耗的次数 let v = (inventory[i] - inventory[i + 1]) * (i + 1) // 当前剩余的次数比需要消耗的次数大,且索引没有到数组的最后一位,则继续往后移 if (orders > v && i < inventory.length - 1) { orders -= v i++ } else { // 计算能被所有列消耗一样的次数 let n = Math.floor(orders / (i + 1)) // 计算每一列的最小值 min = inventory[i] - n // 计算被每一列消耗次数之后剩余的次数,该次数必定小于i orders -= n * (i + 1) flag = false } } // 然后统计每一列能被消耗的最大次数,所有列最小值都一样 while(i >= 0) { res += geth(inventory[i], inventory[i] - min) i-- } // 返回值还得加上不能取整剩余的次数:剩余次数 * 最小值,然后取余 1e9 + 7 return (res + BigInt(orders * min)) % BigInt(1e9 + 7) }; // 获取累加方法: (最大值 + 起始值) * 累加次数 / 2 // 比如要获取最大数100,从上往下累加70次,那么起始位置为31 // 公式:(100 + 100 - 70 + 1) * 70 / 2 ---> (100 + 31) * 70 / 2 /** * num 需要累加的最大值 * orders 需要累加的次数 */ function geth(num, orders) { return BigInt(num + num - orders + 1) * BigInt(orders) / BigInt(2) % BigInt(1e9 + 7) }