销售价值减少的颜色球

2021-02-14

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：

1 2	输入：inventory = [2,8,4,10,6], orders = 20 输出：110

示例 4：

1
2
3

输入：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)

二分查找答案

class Solution{
    public int maxProfit(int[] inventory, int orders) {
        int mod = (int)(1e9 + 7);
        // 计算最大值
        int l = 0,r = maxNum(inventory);
        // 答案在0-最大值之间
        while(l < r){
            int mid = l + (r - l) / 2;
            // 如果操作次数小于orders，即当前的操作次数满足orders
            if(provideOrders(inventory, mid) <= orders){
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        // 注意边界条件是l
        long res = 0;
        for(int num : inventory){
            if(num >= l){
                orders -= (num - l + 1);
                long first = l, last = num, n = num - l + 1;
                // 等差数列求和等差是1
                res = (res + ((first + last) * n / 2) % mod) % mod;
            }
        }
        // 这一步没想明白
        res = (res + (long)orders * (l - 1) % mod) % mod;
        return (int) res;
    }
    // 计算操作的次数
    private long provideOrders(int[] inventory,int m){
        long orders = 0;
        for(int num : inventory){
            orders += Math.max(num - m + 1,0);
        }
        return orders;
    }
    //查找最大值
    private int maxNum(int[] inventory){
        int max = 0;
        for(int num : inventory){
            max = Math.max(max,num);
        }
        return max;
    }
}


class Solution {
  
    public int maxProfit(int[] inventory, int orders) {
        long res = 0;
        if(inventory.length==0||orders==0) return (int)res;
        long max = (long) Math.pow(10, 9)+7;
        if(inventory.length==1){
            res+=sum(inventory[0],inventory[0]-orders);
            return (int)(res%max);
        }
        Arrays.sort(inventory);
        int len = inventory.length;
        int gap[] = new int[len];
        for(int i=0;i<len;i++){
            if(i==0){
                gap[i] = inventory[i];
            }else {
            gap[i] =inventory[i]-inventory[i-1];
            }
        }
        for(int i=1;;i++){
            if(gap[gap.length-i]*i<=orders) {
                res+=i*sum(inventory[len-i],inventory[len-i-1]);
                orders -= i*gap[gap.length-i];
            }else {
                long n= orders%i;
                long x = orders/i;
                res += i * sum(inventory[len - i], inventory[len - i] - (int)x);
                res += n*(inventory[len-i]-x);
                break;
            }
        }
        return (int)(res%max);
    }
    public long sum(int max,int min){
        long n = max - min;
        long s = n*(min+1)+ n*(n-1)/2;
        return s;
    }
}

作者：ljw-5
链接：https://leetcode-cn.com/problems/sell-diminishing-valued-colored-balls/solution/chao-guo-suo-you-java-ti-jiao-zhong-ji-bai-liao-10/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。