leetcode算法：1648. 销售价值减少的颜色球

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了leetcode算法：1648. 销售价值减少的颜色球，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2048字，纯文字阅读大概需要3分钟。

内容图文

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

 

内容总结

以上是互联网集市为您收集整理的leetcode算法：1648. 销售价值减少的颜色球全部内容，希望文章能够帮你解决leetcode算法：1648. 销售价值减少的颜色球所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---