题解

思路

假设把若干怪物交给水系魔法处理，它们的力量和为 $x$；其余怪物交给火系魔法处理，力量和为 $S-x$。完成这两部分分别需要

$$\left\lceil\frac{x}{w}\right\rceil,\qquad \left\lceil\frac{S-x}{f}\right\rceil$$

秒。两种魔力同时产生，因此这种分配的完成时间是二者的最大值。问题转化为：在所有可由怪物力量组成的子集和 $x$ 中，最小化上述最大值。

做法

当 $n\le20$ 时，可以枚举全部子集，直接计算每个子集和对应的完成时间。

在第二个子任务中，若 $n\le20$ 仍使用子集枚举；否则力量总和不超过 $20000$，可以用普通一维背包数组求出全部可达子集和。

完整数据中，力量总和最多为 $10^6$。用位集合表示可达子集和：初始只有和 $0$ 可达；加入力量 $s_i$ 时，将当前位集合左移 $s_i$ 位并与原集合取或。全部处理后枚举可达的 $x$，计算对应时间并取最小值。

正确性证明

每个怪物必须且只会由一种魔法击败，因此任何方案都唯一对应一个交给水系魔法的怪物子集。若该子集力量和为 $x$，水系至少需要 $\lceil x/w\rceil$ 秒，火系至少需要 $\lceil(S-x)/f\rceil$ 秒；两种魔力并行产生，所以方案完成时间恰为两者最大值。

背包转移在加入每个怪物时保留“不选择它”的全部子集和，并把“选择它”的子集和整体增加 $s_i$，故处理完所有怪物后，位集合恰好表示所有可能的水系力量和。算法枚举其中每个可达值并取最小完成时间，因此不会遗漏任何合法分配，也不会考虑非法分配，所得即为最短时间。

复杂度

设 $S=\sum s_i$。

• 子集枚举的时间复杂度为 $O(2^n n)$，空间复杂度为 $O(n)$；
• 普通背包的时间复杂度为 $O(nS)$，空间复杂度为 $O(S)$；
• 位集合背包的时间复杂度为 $O(nS/64+S)$，空间复杂度为 $O(S)$。