题解：AT_abc442_g [ABC442G] Lightweight Knapsack

deepthinker · 2026-01-25 22:15:02 · 题解

纪念第 n 次 AK abc。

思路

重量只有三种，这是关键突破口。

物品数量可以很大（10^9），不能直接 DP。

对于同重量物品，我们显然优先选价值高的。

主要思路 我们将物品按重量分成三组：

重量 1 的物品组 g1

重量 2 的物品组 g2

重量 3 的物品组 g3

对于每组，我们按价值从高到低排序，并计算前缀和，这样可以快速求出取某个数量的物品能获得的最大价值。

具体方法

预处理每组物品，按价值降序排序，计算前缀数量和前缀价值，然后用三分搜索：

• 设我们取 x 个重量为 3 的物品，则：花费重量：3x剩余容量：R = C - 3x，问题转化为：用容量 R 装重量 1 和 2 的物品，求最大价值。

• 对于容量 R，设我们取 y 个重量为 2 的物品，则：

花费重量：2y

剩余容量：R - 2y

这个容量全装重量 1 的物品。

总价值 = g2.gs(y) + g1.gs(R - 2y)

由于 g1.gs() 和 g2.gs() 都是凹函数（离散意义下），我们可以在 y 的取值范围 [0, \min(g2.tc, R/2)] 内进行三分搜索，找到最优的 y。

外层三分搜索 同样，F(x) = g3.gs(x) + G(R) 在 x 的取值范围 [0, \min(g3.tc, C/3)] 内也是凹函数，我们可以再次使用三分搜索找到最优的 x。

其中：

Gp.bd(): 对组内物品排序并计算前缀和。

Gp.gs(x): 快速计算取前 x 个物品的总价值。

G(R): 求解容量 R 下重量 1 和 2 物品的最优组合。

F(x): 求解取 x 个重量 3 物品时的总价值。

注意！

使用 vector 存储物品，排序后计算前缀和。

三分搜索时注意整数处理，搜索区间缩小到足够小后暴力枚举。

注意 long long 类型，避免溢出。