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

2023-05-07 HGNULB 约 7 分钟

文章信息 6 个分类 6 个标签

分类

题目描述

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

题意分析

inventory[i] 表示第 i 种颜色现有多少个球。卖出一个球，收到的钱等于卖之前该颜色的剩余数量，卖完这一个之后该颜色的数量减一。必须恰好卖出 orders 个球，问总收入最大是多少，结果对 $10^9 + 7$ 取模。

换个角度看会清楚很多：一种颜色若原有 v 个球，把它们全部卖光的收入依次是 v, v-1, …, 1。也就是说，每种颜色提供的其实是一串从 v 递减到 1 的"价签"，我们要从所有颜色的价签里挑出 orders 张，使总和最大。约束是同一种颜色的价签必须从大到小依次取，不能跳着取——但既然目标是最大化，这个约束天然满足，不构成限制。

于是问题被剥成一句话：从若干个「1 到 $v_i$ 的整数集合」的并集（可重集）里取 orders 个数，使和最大。

数据规模决定了做法：颜色数最多 $10^5$，但 $v_i$ 最大 $10^9$，orders 最大 $10^9$。逐个卖球是 $10^9$ 次操作，超时；用堆每次取最大值再放回，同样是 orders 次操作，一样超时。$v_i$ 高达 $10^9$ 这一点强烈暗示：答案必须按「价格档位」批量结算，而不是按「球」逐个结算。

取模只作用在最终答案上，中间的「还剩多少订单」「某档位卖多少个」都是真实计数，绝不能取模。这一点是本题最隐蔽的坑。

边界包括：orders 恰好等于所有球的总数（全部卖光）；所有颜色数量相同；只有一种颜色；以及 orders 小到只需卖掉最高档位的一部分。

解法：贪心 + 二分查找

核心思路

每种颜色库存为 v 时，依次卖出的价格是 v, v-1, ..., 1。因此问题等价于从所有价格序列中取最大的 orders 项。只要尚有更高价格可卖，就不应选择更低价格；交换这两次销售会严格提高收益。

最优结果因此存在一个价格水平线 level：所有高于它的价格全部卖出，再以 level 的价格卖出少量球补齐订单。定义
\[sold(x)=\sum_i\max(0,inventory_i-x)\]
它表示把每种库存降到至多 x 时卖出的球数。x 越大，sold(x) 越小，所以可以二分寻找满足 sold(x) <= orders 的最小 x。

对每个 v > level，已卖价格是从 level + 1 到 v 的完整等差段，数量为 v - level，收益为
\[\frac{(level+1+v)(v-level)}{2}\]
这些整段卖完后，剩余 orders - sold(level) 个订单都按 level 计价。由 level 的最小性，若 level > 0，则 sold(level-1) > orders，所以当前处于 level 的可售颜色足够补齐余数。

代码不逐球模拟；计数、乘积和累计收益均使用 64 位整数，只有收益累加时取模，订单数量本身不能取模。

解题步骤

扫描库存得到最大值，二分区间设为 [0, maxInventory]。

对中点计算 sold(mid)。若不超过 orders，保留中点并收缩右边界；否则提高左边界。

二分结束后，遍历每个高于 level 的库存，用等差数列公式批量累加完整价格段，并统计已卖数量。

将剩余订单乘以 level，加入收益后取模返回。

例如 inventory = [2,5], orders = 4。最小可行水平线为 2：高于 2 的完整价格段是 5+4+3=12，已卖 3 个；最后一个球卖 2，总收益为 14。

当订单等于球总数时，level = 0 且没有余数；只有一个订单时，水平线会停在最高库存附近，只卖出全局最高价。

代码实现

class Solution {
    private static final long MOD = 1_000_000_007L;

    public int maxProfit(int[] inventory, int orders) {
        int maxInventory = 0;
        for (int value : inventory) {
            maxInventory = Math.max(maxInventory, value);
        }

        int left = 0;
        int right = maxInventory;
        while (left < right) {
            int mid = left + (right - left) / 2;
            long sold = 0;
            for (int value : inventory) {
                if (value > mid) {
                    sold += value - mid;
                    if (sold > orders) {
                        break;
                    }
                }
            }
            if (sold <= orders) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        int level = left;
        long sold = 0;
        long profit = 0;
        for (int value : inventory) {
            if (value > level) {
                long count = value - level;
                long segment = ((long) level + 1 + value) * count / 2;
                profit = (profit + segment) % MOD;
                sold += count;
            }
        }
        long remaining = orders - sold;
        profit = (profit + remaining * level) % MOD;
        return (int) profit;
    }
}

func maxProfit(inventory []int, orders int) int {
	const mod int64 = 1_000_000_007

	maxInventory := 0
	for _, value := range inventory {
		if value > maxInventory {
			maxInventory = value
		}
	}

	left, right := 0, maxInventory
	for left < right {
		mid := left + (right-left)/2
		var sold int64
		for _, value := range inventory {
			if value > mid {
				sold += int64(value - mid)
				if sold > int64(orders) {
					break
				}
			}
		}
		if sold <= int64(orders) {
			right = mid
		} else {
			left = mid + 1
		}
	}

	level := left
	var sold, profit int64
	for _, value := range inventory {
		if value > level {
			count := int64(value - level)
			segment := (int64(level) + 1 + int64(value)) * count / 2
			profit = (profit + segment) % mod
			sold += count
		}
	}
	remaining := int64(orders) - sold
	profit = (profit + remaining*int64(level)) % mod
	return int(profit)
}

复杂度分析

时间复杂度：$O(n\log V)$，其中 $n$ 是颜色数、$V$ 是最大库存。二分每轮扫描数组，结算再扫描一次。

空间复杂度：$O(1)$，只使用常数个标量，没有排序或额外容器。

关键点总结

贪心的本质是始终选择当前最高价格，水平线把逐球操作压成整段结算。

sold(x) 单调不增，二分寻找的是满足订单上限的最小水平线。

完整段使用等差数列求和，余数统一按水平线价格结算。

销量必须保留真实值；取模只作用于收益。

二分计数、等差乘积和答案都要使用 64 位整数。

易错点总结

用 32 位整数累计 sold 或等差乘积会溢出；大量高库存时计数可远超 int。

二分方向写反：sold(mid) > orders 表示水平线太低，必须提高左边界。

等差段漏掉 level + 1。库存 5 降到 2 应结算 3+4+5=12。

在等差数列完成整数除法前取模，会破坏“乘积必为偶数”的性质。

对剩余订单数取模会破坏真实销量，导致尾段数量错误。

逐球使用堆虽贪心正确，但 orders 很大时会超时。

相似题目

题目	难度	考察点
875. 爱吃香蕉的珂珂	中等	二分的对象是速度，判定函数用向上取整算耗时，是答案二分的入门形态
1011. 在 D 天内送达包裹的能力	中等	二分运载能力，判定需按顺序装箱不可重排，左端点必须取单件最大值
1482. 制作 m 束花所需的最少天数	中等	二分天数，判定要统计连续段个数，还要先排除总量不足的无解情况
410. 分割数组的最大值	困难	二分子数组和的上界，判定用贪心分段，也可用区间 DP 对照验证
774. 最小化去加油站的最大距离	困难	答案是实数，二分要按精度而非整数收敛，终止条件写法完全不同
1675. 数组的最小偏移量	困难	同样是「按层削平」的直觉，但操作可逆且不可批量，只能靠堆逐步下降
1046. 最后一块石头的重量	简单	堆模拟的标准形态，操作次数与元素数同阶，恰好是本题堆解法可行时的样子
2462. 雇佣 K 位工人的总代价	中等	也要按最优顺序批量取最小代价，但候选来自双端窗口，必须用两个堆维护