题解

思路

从左到右暂时喝下每瓶药水。若生命值变为负数，当前选择集合必须删除至少一瓶；删除效果值最小的药水能让生命值增加最多，并且不会减少已喝数量之外的任何优势。

用小根堆维护已选择药水的效果，即可随时找到最差的一瓶。

做法

维护当前生命值 health 和小根堆。对每个 $a_i$：

1. 把它加入生命值和堆；
2. 若生命值为负，弹出堆中最小值，并从总和中减去它。

处理结束后，堆大小就是最多能喝的药水数。

正确性证明

处理任一前缀后，算法的选择集合生命值非负。若加入新药水后仍非负，保留它显然不会减少选择数。若变为负数，任何可行的同大小集合都不存在，必须删除至少一瓶；删除最小效果值使删除后的生命值最大，因此在选择数减少一的所有方案中，对未来最有利。

归纳可得，每个前缀处理后，算法在最大选择数量下拥有不小于任何其他方案的生命值，故不会错过后续可行选择。最终堆大小全局最大。

复杂度分析

每瓶药水至多入堆和出堆一次，时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。

子任务说明

• $n\le20$ 时枚举所有子集。
• $n\le300$ 时按已喝数量做 $O(n^2)$ 动态规划。
• 满数据使用小根堆维护最差已选药水。