LeetCode 1648. 销售价值减少的颜色球
题目描述
题意分析
某种颜色还剩多少球，下一个球就能卖多少钱，卖出后该颜色库存减一。需要恰好卖出
orders个球，使总收入最大，最后对 $10^9+7$ 取模。订单数可能很大，不能逐个球模拟销售。
解法：贪心 + 二分查找
核心思路
[!blue]
库存为value的一种颜色，会依次产生value, value-1, ..., 1的销售价格。最大收入就是从所有颜色的价格序列中选择最高的orders项。这样的选择也符合实际销售顺序：选到某个低价前，它同色的所有更高价格都会先被选中。用价格水平线
level分成两部分：所有高于它的价格完整卖出，再用价格恰好等于它的球补足订单。给定水平线 $x$，完整高价段的数量为 $sold(x)=\sum_i\max(0,inventory[i]-x)$。水平线越高，这个数量越少，因此可以二分最小的满足sold(x) <= orders的 $x$。搜索范围是 $0$ 到最大库存。若高价段数量超过订单，说明水平线太低，令左边界越过中点；否则保留中点并收缩右边界。得到的
level保证完整高价段不会超卖。当
level > 0时，由最小性可知sold(level) <= orders < sold(level-1)。两次计数之差，正好是能再以level卖出一个球的颜色数量，所以足够填满剩余订单。若level = 0，题目又保证订单不超过总库存，只能是全部库存恰好卖完，剩余订单为零。库存大于
level的颜色贡献价格段level+1到value，用等差公式(level+1+value) * (value-level) / 2一次求和。最后加上remaining * level。乘法先用 $64$ 位整数完成，再做整数除法与收益取模；销量始终保留真实数值，不参与取模。
解题步骤
- 取得最大库存，二分最低可行水平线。
- 每轮累加高于中点的销量，超过订单即可停止计数。
- 按等差公式结算所有完整高价段。
- 剩余订单乘以水平线价格，加入收益后取模。
代码实现
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+1))$，V 为最大库存，每轮判定扫描全部颜色。
- 空间复杂度：$O(1)$，只维护计数和收益。
关键点总结
[!green]
- 高于水平线的全部出售，等于水平线的按需出售。
- 整段等差求和替代逐球模拟。
- 乘积先使用 64 位完成整数除法，再参与取模累加。
- 二分中的销量计数只用于判断，可提前结束；最终结算重新统计完整高价段。
易错点总结
[!yellow]
- 销量太多时继续降低水平线：会卖出更多，应提高下界。
- 等差段从 level 开始计算：把待补的边界价格重复计入完整段。
- 对订单数量取模：破坏真实销售数量。
- 直接先对等差乘积取模再除二：普通整数除法不再等价。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 378. 有序矩阵中第 K 小的元素 | 中等 | 每种颜色的收益形成一条有序递减序列，本题取全局前若干项并求和，可按收益层批量计数而不逐球模拟。 |