攻略地下城

当前等级为 $X$ 时，只需考虑满足 $A_i < X$ 的地下城。挑战不满足该条件的地下城不会提升等级，因此不可能优于之后再挑战该地下城。

在满足 $A_i < X$ 的地下城中，选择 $B_i$ 最小的地下城。若当前等级为 $X$，所选地下城的第二个难度值为 $B$，则攻略后的等级为

$$X+\min(X,B)$$

。

设当前可以攻略的两个地下城的第二个难度值满足 $b \leq c$，则按照 $b,c$ 的顺序攻略这两个地下城后得到的等级，不小于按照 $c,b$ 的顺序攻略后得到的等级。反复应用这一交换论证可知，优先选择当前可以攻略的地下城中 $B_i$ 最小的地下城，不会失去最优解。

将地下城按照 $A_i$ 升序排序。把所有满足 $A_i$ 小于当前等级的地下城的 $B_i$ 加入最小堆，然后从堆中取出最小值并更新等级。如果堆为空，则剩余的所有地下城都无法使等级提升，因此结束算法。

时间复杂度为 $O(N\log N)$，空间复杂度为 $O(N)$。最终等级不超过 $L+\sum B_i$，因此不超过 ，处于有符号 64 位整数的取值范围内。

Solution written by GPT5